ever heard of this? try to get some information on wikipedia...

it is an UNSOLVED mathematical problem..

if an integer number is odd then it will proccessd by 3n+1

if an integer is not odd then it will be processed by n / 2

odd = n mod 2

this will repeat until n reaches 1..

and then an infinity sequence of 4,2,1,4,2,1 will haappen..

so what the... why is this described as an unsolved problem?

if n is of power of 2 it will always get divided by 2 and if its then 2 a 3*1+1 is happening.. and then its again 4 and the algo is stuck in 4,2,1....

why the hell is this an unsolved mathematical problem????

as you will see collatz 23 outputs:

70,35... .. ... 5 .. until it reaches 16 16 is power of 2.. and the thing described above will happen..

so it is totally sensless how big the numbers will rise.. if they are power of two then it will result in 4,2,1...

don't blame me for posting this.. but am i a genius or all others be blind.. or i don't get the whole point...

it is an UNSOLVED mathematical problem..

if an integer number is odd then it will proccessd by 3n+1

if an integer is not odd then it will be processed by n / 2

odd = n mod 2

this will repeat until n reaches 1..

and then an infinity sequence of 4,2,1,4,2,1 will haappen..

so what the... why is this described as an unsolved problem?

if n is of power of 2 it will always get divided by 2 and if its then 2 a 3*1+1 is happening.. and then its again 4 and the algo is stuck in 4,2,1....

why the hell is this an unsolved mathematical problem????

`main`

call collatz 23

func collatz(int n)

while n > 1

show n

if n mod 2 = 0 Then

n = 3 * n + 1

else

n = n / 2

end if

wend

show n

end func

as you will see collatz 23 outputs:

70,35... .. ... 5 .. until it reaches 16 16 is power of 2.. and the thing described above will happen..

so it is totally sensless how big the numbers will rise.. if they are power of two then it will result in 4,2,1...

don't blame me for posting this.. but am i a genius or all others be blind.. or i don't get the whole point...

What you've shown isn't a mathematical proof, it requires running the program...

hmm that's a point.. guess I try to figure it out this evening :lol:

We are either geniuses, or fools, because I, too, can't see where is the problem.

- multiplying by 3 and adding 1 will always produce an even number, thus enabling a division in next turn

- dividing by 2 will much more likelky produce an even number, thus enabling even further division. and this likeness is greater than 2:3

so the number, in long run, must decrease.

or am I missing something? o_O ?

- multiplying by 3 and adding 1 will always produce an even number, thus enabling a division in next turn

- dividing by 2 will much more likelky produce an even number, thus enabling even further division. and this likeness is greater than 2:3

so the number, in long run, must decrease.

or am I missing something? o_O ?

- multiplying by 3 and adding 1 will always produce an even number, thus enabling a division in next turn

3*1 + 1 = 4 Even

3*2 + 1 = 7 Odd

3*3 + 1 = 10 Even

3*4 + 1 = 13 Odd

3*5 + 1 = 16 Even

:roll:

And dividing by two perhaps statistically will produce an even number, but obviously there are Ns that are even numbers but dividing them by two produces an odd number (like n = 10).

The remark about 3*n + 1 is not appliable to what ti_mo_n is refering to. Check his post below

you multiply by 3 and add 1 only if the number is odd (I was reffering to the "problem", not to numbers in general ;) ). even numbers have to be divided by 2.

about the second thing: even numbers end with 0, 2, 4, 6, 8. among them, (adequately large) numbers ending with 0, 4, and 8 will produce further divisions in next turn.

so, statistically, the sequence is supposed to AT MOST (the most pessimistic scenario) stop. It can never rise, because for every 2 multiplications by 3, there are 3 divisions by 2. And this is the MOST pessimistic scenario. Computers can prove that up to, like, 2^64 the sequence DECREASES, so I see absolutely NO reason, why any larger number should lock in a dead loop (produce a cycle and thus never reach 1). In other words: if a number like 738472992384 decreases to 1, then why "xxxxxxxxxxxxxxx738472992384" [x being any digit) should not? If the "738472992384" will decrease then this "xxxxxxxxxxxxxxx738472992384" wil also decrease to AT LEAST "xxxxxxxxxxxxxxx1" (because "738472992384" decreases to 1), and then you multiply it by 3, which will produce an even number, and -statistically- two divisions of it. So the number"xxxxxxxxxxxxxxx1" should -statistically- decrease by 3:2 in ~4 turns. And then just repeat the process: once again you get some number, with some ending. And that ending has beed proved to decrease to 1, so.......... and so on, and so on.

about the second thing: even numbers end with 0, 2, 4, 6, 8. among them, (adequately large) numbers ending with 0, 4, and 8 will produce further divisions in next turn.

so, statistically, the sequence is supposed to AT MOST (the most pessimistic scenario) stop. It can never rise, because for every 2 multiplications by 3, there are 3 divisions by 2. And this is the MOST pessimistic scenario. Computers can prove that up to, like, 2^64 the sequence DECREASES, so I see absolutely NO reason, why any larger number should lock in a dead loop (produce a cycle and thus never reach 1). In other words: if a number like 738472992384 decreases to 1, then why "xxxxxxxxxxxxxxx738472992384" [x being any digit) should not? If the "738472992384" will decrease then this "xxxxxxxxxxxxxxx738472992384" wil also decrease to AT LEAST "xxxxxxxxxxxxxxx1" (because "738472992384" decreases to 1), and then you multiply it by 3, which will produce an even number, and -statistically- two divisions of it. So the number"xxxxxxxxxxxxxxx1" should -statistically- decrease by 3:2 in ~4 turns. And then just repeat the process: once again you get some number, with some ending. And that ending has beed proved to decrease to 1, so.......... and so on, and so on.

you multiply by 3 and add 1 only if the number is odd (I was reffering to the "problem", not to numbers in general ;) ). even numbers have to be divided by 2.

The remark was very stupid from my part then :P

Yes it's just like f0dder said.. theres just no mathematical written formular or proof but the logic is easy to follow everyone can imagine after a while why the numbers will decrease.. but I think I even figured out an mathematical proof or at least a starting point yesterday but I'm not at home right now so I cant lookup it was something like

(3*n+1)=2^x

if you solve it to n you get

n=(2^x-1)/3

that means n for the case of an power of 2 number..

so if you put this n into the formular 3*n+1

3*((2^x-1)/3)+1

then every number of x will result in an power of 2

so that means just that 3n+1 will come to a power of 2 of course and if this happens then

(3*((2^x-1)/3)+1)/(2^x)

where 2^x just represents the div n 2 the times needed for coming to 1

it will always result in 1....

(3*n+1)=2^x

if you solve it to n you get

n=(2^x-1)/3

that means n for the case of an power of 2 number..

so if you put this n into the formular 3*n+1

3*((2^x-1)/3)+1

then every number of x will result in an power of 2

so that means just that 3n+1 will come to a power of 2 of course and if this happens then

(3*((2^x-1)/3)+1)/(2^x)

where 2^x just represents the div n 2 the times needed for coming to 1

it will always result in 1....

Hello to all.

I knew of this "problem" in the early 90s, (or late 80s?) in Scientific american, (it was called "hailstone numbers).

I have made some research runing a program, (is easy to code) all the time the series hits a power of 2, and plumet to the 4,2, 1 cycle. Every time, the series hits the 2^n precipice.

But the problem is unsolved because *** In imposible to prove that it will always do so***

it means that in the wole domain of natural numbers, there could be a cycle diferent from the 4,2,1 and who never leads to a power of 2. AFAYK there is no such cycle, but THERE IS NO WAY TO PROVE IT, or disprove either.

this is not as frivolous as it semes, it points to a deep and serious flaw in the matemathical reasoning, for a beter and extended expalantion see "Godel Echer and Bach an eternal golden braid"

saludos

Carlos Pacheco

I knew of this "problem" in the early 90s, (or late 80s?) in Scientific american, (it was called "hailstone numbers).

I have made some research runing a program, (is easy to code) all the time the series hits a power of 2, and plumet to the 4,2, 1 cycle. Every time, the series hits the 2^n precipice.

But the problem is unsolved because *** In imposible to prove that it will always do so***

it means that in the wole domain of natural numbers, there could be a cycle diferent from the 4,2,1 and who never leads to a power of 2. AFAYK there is no such cycle, but THERE IS NO WAY TO PROVE IT, or disprove either.

this is not as frivolous as it semes, it points to a deep and serious flaw in the matemathical reasoning, for a beter and extended expalantion see "Godel Echer and Bach an eternal golden braid"

saludos

Carlos Pacheco

I am familiar with that book, I don't know how it relates to this problem.

As for Proof, you must mean mathematical proof, not empirical proof, which is the philosophical proof and the natural truth.

As for Proof, you must mean mathematical proof, not empirical proof, which is the philosophical proof and the natural truth.

Hi Homer,

It's related, by the central theme of the book, the "Godel incompletenes theorem", who states that any formal system (like mathematics, logic etc), no mater how powerfull, is not powerfull enoght to "look" into it's inards, that there will be some truths and falsities in the formal system (known or not) that can be deduced by the same system.

This is the reason you can have empirical proof, by making the calculations by hand or by computer, that the 3n+1, n/2 problem is finite, (it hits the 4,2,1 secuence), but not mathematical proof of it, mathematics is not powerfull enought to reach this trut.

And its not the only trut, there hare many more that haunt the mathematicians, and it's not fixed by "refining" mathematics, cause "It's not a bug, it's a feature" ;)

Saludos

Carlos Pacheco

It's related, by the central theme of the book, the "Godel incompletenes theorem", who states that any formal system (like mathematics, logic etc), no mater how powerfull, is not powerfull enoght to "look" into it's inards, that there will be some truths and falsities in the formal system (known or not) that can be deduced by the same system.

This is the reason you can have empirical proof, by making the calculations by hand or by computer, that the 3n+1, n/2 problem is finite, (it hits the 4,2,1 secuence), but not mathematical proof of it, mathematics is not powerfull enought to reach this trut.

And its not the only trut, there hare many more that haunt the mathematicians, and it's not fixed by "refining" mathematics, cause "It's not a bug, it's a feature" ;)

Saludos

Carlos Pacheco

1. Every number can be expressed in form "x+y", where y is less than 2^64, the sequence is proved to decrease to the "4, 2, 1" cycle.

2. x may be presented in a "x1 + x2 + x3 + ..... + xn" form where each of these xs are less than, or equal y.

3. if each of these xs decrease to 1 (because every number less than or equal to y does), then they form something like "1+1+1+1+1+1+......" which yields a number

4. treat this new number as another, new, "x+y"

5. go to 1 until the number if finite and less than 2^64.

7. It is proved that this number will decrease to 1.

Isn't it proof enough?

2. x may be presented in a "x1 + x2 + x3 + ..... + xn" form where each of these xs are less than, or equal y.

3. if each of these xs decrease to 1 (because every number less than or equal to y does), then they form something like "1+1+1+1+1+1+......" which yields a number

4. treat this new number as another, new, "x+y"

5. go to 1 until the number if finite and less than 2^64.

7. It is proved that this number will decrease to 1.

Isn't it proof enough?

Hi ti_mo_n

No it is not, the problem is the statement "where y is les than 2^64", it is a artificial boundary, and in mathematlcal induction this is a no-no, the reasonign sould be true for ALL numbers, not just numbers below a limit, it's ike saying "I found a formula to compute prime numbers below the 2^16 limit" if the formula fails over these limits, then it's not a general formula, end the problem remains unsolved.

Salu2

Carlos

No it is not, the problem is the statement "where y is les than 2^64", it is a artificial boundary, and in mathematlcal induction this is a no-no, the reasonign sould be true for ALL numbers, not just numbers below a limit, it's ike saying "I found a formula to compute prime numbers below the 2^16 limit" if the formula fails over these limits, then it's not a general formula, end the problem remains unsolved.

Salu2

Carlos

Hi Carlos.

OK, I see your point. Sure, maths is bugged :P

OK, I see your point. Sure, maths is bugged :P

The central theme of the book is not godel's incompleteness theorem, its the interaction and sameness of the three fields of mathematics, visual art and musical composition.

I can understand that you are driven by math, and see math as the centerpiece of that work.

But that was not the intention of the author.

He was implying that there is an underlying homogeny and harmony between these fields, and that with perspective, each can be viewed as a work of another field.

He was implying that there is a common chord, a uniting theme, which he failed to describe, but nonetheless I agree with his perception in this regard.

I can understand that you are driven by math, and see math as the centerpiece of that work.

But that was not the intention of the author.

He was implying that there is an underlying homogeny and harmony between these fields, and that with perspective, each can be viewed as a work of another field.

He was implying that there is a common chord, a uniting theme, which he failed to describe, but nonetheless I agree with his perception in this regard.

`; Collatz Conjecture:`

mov eax,Test_Number ; try 27

jmp _0

_1: lea eax,

_0: shr eax,1

je _x

jc _1

jmp _0

_x:

Very easy to test smaller numbers. (c: I read that building a cycle tree can allow very large numbers to be tested. Certainly, not a proof of anything - no one has found a case that fails. I find it easy to think about the bit pattern of the number and know it will always reach one (i.e. carry flag set on exit). Multiplying by three and adding one has the effect of moving the one bits higher - they will all eventually carry to a single bit.Imagine the number bits can be cut down the middle lengthwise - so we have two copies. Now stack up the copies, shifting the top copy over one bit - we add one, so that space is a one bit. We don't have to add the whole thing - just count the bits in the least column. There is two one bits because it was odd.

It's tempting to do the addition and work with smaller numbers, but if you keep duplicating the whole stack and shifting it then it's easier to see how it'll always result in a power of 2. Really, should show some pictures - much easier to see.

For example the sequence for 7: 7 22 11 34 17 52 26 13 40 20 10 5 16.

If we didn't divide by two, it would be:

`7`

22

68 = 22*3 + 2

208 = 68*3 + 4

640 = 208*3 + 16

2048 = 640*3 + 128

mov eax,7

_0: bsf edx,eax

xor ecx,ecx

lea eax,

bts ecx,edx

cmp eax,ecx

je _x

add eax,ecx

jmp _0:

_x:

The divide by two step just keeps the numbers smaller. Clearly, the least bit is being propagated to fill the zero holes between the least and most significant set bit, but how can one explain mathematically that this is so?Here is a general routine to test

- only touches needed memory

- doesn't shift bignum (divide by two)

- doesn't test whole bignum for exit

It's all in L1 cache, and pretty fast, too! The wrap around buffer idea works like a FIFO - consuming one bits at the tail, while the head advances.

Edit: there is an error in it somewhere, but I'm done with it for now.

**very**large numbers. :)- only touches needed memory

- doesn't shift bignum (divide by two)

- doesn't test whole bignum for exit

`use32`

TestBuffer rb 32*1024 ; 32k

; a big number to test: 2^65536 + 3

mov dword ,3

mov dword ,1

push 32*1024/4 ; L1 cache size (c:

push TestBuffer

call CollatzArrayQ

jc ErrorNeedBiggerBuffer

; check Collatz Conjecture on multi-percision number

;

; carry flag set on array overflow

; carry flag clear on pass

; (otherwise it loops forever: not likely, but hasn't been proven)

;

; NOTE: array should be twice the size of number to test - too large

; is not a problem as only active bits are operated on.

CollatzArrayQ:

label .arr at esp+4+32

label .len at esp+8+32

pushad

mov ebx,[.arr]

mov eax,[.len]

mov ecx,1

mov esi,ebx

lea ebp,

; address past number in EDI (active end marker)

; (need at least one zero dword on end!)

.z: dec eax

test dword ,-1

je .z

lea edi,

cmp edi,ebp

je .over

; advance to lowest set bit

.0: test ,ecx

jne .1

rol ecx,1

jnc .0 ; HINT: taken

add esi,4

cmp esi,ebp ; end

cmovnc esi,ebx ; reset

jmp .0

; ESI is first set bit, multiply by three and add ESI

; all (virtual) lower bits are zero.

.1:

; test if buffer is == ESI then done!

cmp ,ecx

jne .kx ; HINT: taken

; if EDI==ESI+4 or (ESI+4==EBP && EDI==EBX)

; (faster than testing all of buffer)

mov edx,edi

lea eax,

cmp edi,ebx

cmove edx,ebp

cmp eax,edx

je .x

.kx:

push ecx

push esi

.2:

xor edx,edx

add ecx,

adc edx,0

shl dword ,1

adc edx,0

add ,ecx

adc edx,0

mov ecx,edx

add esi,4

cmp esi,ebp ; end

cmovnc esi,ebx ; reset

cmp esi,edi

jne .2

test ecx,ecx

je .5

cmp edi,

je .over

mov ,ecx

add edi,4

cmp edi,ebp ; end

cmovnc edi,ebx ; reset

.5: pop esi

pop ecx

jmp .0

.x: popad

clc

retn 8

.over: popad

stc

retn 8

(FASM syntax)It's all in L1 cache, and pretty fast, too! The wrap around buffer idea works like a FIFO - consuming one bits at the tail, while the head advances.

Edit: there is an error in it somewhere, but I'm done with it for now.

Status of the 3x+1 class record progress as of: Dec 13, 2007. Intervals are indicated in blocks of 20,000,000,000,000 (20 E+12 or 20 trillion numbers). Calculation of a single block takes approximately 20 days of (idle) time on a Pentium 1000 MHz.

Basically, a trillion per day, per Ghz.Naturally, I'm currious how my routine compares:

Currently, they are working on 7 * 2^53 block of numbers. I ran a test of my algorithm for 2^24 numbers (in that block range) which took 38781ms. Which means it is roughly 25 times

**slower**. Their algorithm is tuned for this size and uses very large data structures. I might be able to double the speed of my algorithm, but confirming ranges of numbers is not what it's designed for.

The central theme of the book is not godel's incompleteness theorem, its the interaction and sameness of the three fields of mathematics, visual art and musical composition.

I can understand that you are driven by math, and see math as the centerpiece of that work.

But that was not the intention of the author.

He was implying that there is an underlying homogeny and harmony between these fields, and that with perspective, each can be viewed as a work of another field.

He was implying that there is a common chord, a uniting theme, which he failed to describe, but nonetheless I agree with his perception in this regard.

I can understand that you are driven by math, and see math as the centerpiece of that work.

But that was not the intention of the author.

He was implying that there is an underlying homogeny and harmony between these fields, and that with perspective, each can be viewed as a work of another field.

He was implying that there is a common chord, a uniting theme, which he failed to describe, but nonetheless I agree with his perception in this regard.

You are right Homer. the central theme of the book is not Godek 's incompleteness theorem, is artificial inteligence, but the "Hailstone numbers" (3n+1,n/2 prroblem) crops up in one of the chapters (sadly I don have the book at hand to see wich one), very close to the MUI problem, as a early proff of the incompletness theorem

h

Saludos y Feliz aņo nuevo (happy new year)

Carlos