Collatz Proof Proposed: Hailstone Sequences End In 1

mikejuk writes "A proof [preprint PDF] has been proposed for the Collatz conjecture about hailstone sequences. A hailstone sequence starts from any positive integer n the next number in the sequence is n/2 if n is even and 3n+1 if n is odd. The conjecture is that this simple sequence always ends in one. Simple to state but very difficult to prove and it has taken more than 60 years to get close to a solution."

Comments

Re:... and someone finds a fault in the proof.

[Anonymous Coward]

Ok, I'm not a mathematician but when I read:

"What's odd is that this assertion looks on the surface extremely simple. In particular, it is true for any 2l which is divisible by 4, and is true for any 2l I can reasonably imagine... but in the cathedral of mathematics experimental evidence is no evidence at all.

Disclaimer: I am a physics graduate student, not an established mathematician by any means. This is the best I can grok the paper."

I wonder... perhaps the paper's author also thought it was simple and obvious and possibly even proved elsewhere?

Anyway. Isn't refuting the proof, just claiming it is incomplete.
And from what I recall, mathematicians often submit proofs others consider "incomplete" since they kinda assume those things are obvious.

Debunked already

[CSMoran]

Rebuttal of the "proof" here: http://mathlesstraveled.com/2011/06/04/the-collatz-conjecture-is-safe-for-now/

Easy to state, fun to program!

[Terje Mathisen]

I first heard about this conjecture many years ago (25?) and did what most geeks would do; I wrote a program to test all odd integer values and check that they did in fact reach 1.

The obvious approach is to remember the count for each value as you try them, then check any intermediate result against this table:
If found, just add that value to the current count and store the result.

This approach breaks down when you want to test starting values much larger than 2^32, because the space to store the table becomes larger than available memory.

One of the first optimizations is to realize that the result of taking 3n+1 starting from an odd (n) will always be even, so you can simply include the following n/2 (a shift) and increase the count, while getting rid of the multiplication by 3:

Odd(n):
    n = 2m+1
    3n+1 = 6m + 4
    (3n+1)/2 = 3m + 2 = n + (n>>1) + 1

In asm this can be simplified to:

again:
    shr eax,1 ;; Assume even, so divide by two and shift the bottom bit into carry
    jz done ;; If the result of the shift was zero, we're done!

    inc edx ;; Increment number of steps
      jnc again ;; No carry means even input, so go back up

    inc edx ;; One extra increment ;; The starting value was odd, so now we need to multiply by 3 and add 2:
    lea eax,[eax+eax*2+2]
    jmp again

done:

A much more sophisticated step is to see that the next N operations are determined by the bottom N bits of the current value (as long as there are more than N bits available), basically allowing you to convert those N operations into a multiplication, an add and a shift right.

Next you realize that the intermediate values can very quickly overflow a 32-bit unsigned integer, and even using 64-bit values does not get you very far.

My approach back in those days was to use a variable number of 32-bit counters:

With a single counter I check for getting to 1 or overflowing so I need to use two counters.

With two (or more) counters I test for the top counter becoming zero, allowing me to reduce the number of counters, or for overflow forcing another incease.

All of this is of course much easier in asm than C,since you can use the ADD/ADC combination to perform arbitrary precision

Terje