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????

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...
Posted on 2007-11-10 10:55:47 by Emod
What you've shown isn't a mathematical proof, it requires running the program...
Posted on 2007-11-10 11:12:48 by f0dder
hmm that's a point.. guess I try to figure it out this evening :lol:
Posted on 2007-11-10 11:18:18 by Emod
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 ?
Posted on 2007-11-10 14:50:31 by ti_mo_n

- 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
Posted on 2007-11-10 15:12:57 by LocoDelAssembly
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.
Posted on 2007-11-10 15:29:37 by ti_mo_n

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
Posted on 2007-11-10 15:57:21 by LocoDelAssembly
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....
Posted on 2007-11-10 21:34:50 by Emod
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

Posted on 2007-12-09 16:25:18 by Carlos
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.
Posted on 2007-12-10 05:43:56 by Homer
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 
Posted on 2007-12-10 09:46:25 by Carlos
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?
Posted on 2007-12-10 12:04:38 by ti_mo_n
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
Posted on 2007-12-11 10:07:01 by Carlos
Hi Carlos.
OK, I see your point. Sure, maths is bugged :P
Posted on 2007-12-11 20:55:30 by ti_mo_n
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.
Posted on 2007-12-12 05:43:26 by Homer
; 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?
Posted on 2007-12-15 01:28:38 by bitRAKE
Here is a general routine to test 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.
Posted on 2007-12-15 12:49:36 by bitRAKE
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.
Posted on 2007-12-16 11:42:18 by bitRAKE
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.


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
Posted on 2007-12-30 23:55:03 by Carlos