Collatz conjecture

The conjecture is that the hailstone number sequence (aka the 3n+1 sequence) always reaches 1. The truth or falsehood of this conjecture is still not known (hence "conjecture"), although it appears that the choice of numbers (3,1 and 2) is particularly problematic.

No useful encoding for the sequence is known, so it seems that Gödelizing the problem won't work, either.

Pick any natural number, and repeat the following:

• If the number is odd, multiply by 3 and add 1
• Else the number is even; divide it by 2

For instance, if we start from 3, we obtain the sequence 3 10 5 16 8 4 2 1. Note that from 1 we go back to 4, and remain in the 4-2-1 loop. If we instead started from 31, we'd have a slightly more exciting ride: 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 but again we reach 1.

The sequence is named for hailstones, since the process is much like the formation of a hailstone: start with a drop of water, which falls until it hits strong winds. These blow it back up, where a layer of ice is formed; then the stone starts falling down again. This process repeats itself in hailstones; do you know if all hailstones formed in this manner reach the ground? (Well, yes, because not every day is cloudy...)

Is it always the case that we reach 1? Nobody knows! The Collatz conjecture is that the process always reaches 1; it has been verified on computer for enormous numbers, and never been falsified. But this is not a proof, of course.

There are two ways in which the Collatz conjecture could fail:

• There exists some cycle other than the 4-2-1 cycle;
• There exists some number for which the hailstone sequence is unbounded, so we just encounter larger and larger numbers, but never repeat ourselves.

Neither of the possibilities has been ruled out (both must be false for the conjecture to be true).

I used to do this in CS/Math/Physics classes when I was bored. You can easily waste a good twenty minutes per class doing this. But I just found out there's actually a name for it. Anyway, here it is...

Take any natural number greater than 0.
If it's odd, multiply it by 3 and then add 1.
If it's even, divide by 2.
Continue this until you reach the number 1.

Example: 13 ==> 40 ==> 20 ==> 10 ==> 5 ==> 16 ==> 8 ==> 4 ==> 2 ==> 1

This is called the Collatz Problem, and has yet to be proven true for all natural numbers (although it has been verified for all numbers up to 5.6 * 10^13.

Interesting numbers found by making a little program meself (the iterations stop the moment a value is reached that is lower than the initial one, or higher than 1,000,000,000).

   Start  Num  Max Value   Break
--------------------------------
      27   96       9232      23
      31   91       9232      23
      47   88       9232      46
      63   88       9232      61
      71   83       9232      61
     703  132     250504     628
    1055  130     250504     628
    1407  132     250504    1256
    1583  127     250504    1256
    2111  130     250504    1256
    7279  125    1702276    3844
   10087  171    2484916    7688
   12399  122    2480056    8729
   13503  127    1052512   10696
   14695  130    2480056    8729
   15039  135    9635920   10049
   15131  127    2484916   11983
   22559  132    9635920   20098
   26623  106  106358020   26321
   31911   96  121012864   24928
   34239  150   18976192   32572
   35655  220   41163712   29405
   37503  205   35075104   21722
   41407  140    6454384   31123
   45055  181   13699096   43444
   45127  210   41163712   29405
   47867   94  121012864   24928
   50427  106  121012864   49856
   53247  106  106358020   52642
   53851   88  121012864   49856
   56095  119  106358020   52642
   56255  202   35075104   43444
   56731  101  121012864   49856
   57115  200   41163712   29405
   59903  101  106358020   52642
   60583   83  121012864   49856
   60975  207  593279152   52975
   64255  194   41163712   58810
   65307   96  521790496   51014
   67583  176   13699096   57925
   69535  171  593279152   52975
   73471   91  521790496   51014
   73755  132  139841152   65699
   75007  202   35075104   57925
   77031  145   21933016   65134
   77039  125   18976192   40667
   77671  Dno Dunno   1047216490

So 77671 hit the ceiling, as 1,047,216,490 is too high...

Even more peculiar is the number of iterations. To the left is the number of iterations it took to get below the inital value, to the right is the frequency of this happening for all initial values from 1 to 77671.

Num     Frq
------------
  1   38835
  3   19418
  6    4855
  8    4854
 11    1821
 13    2124
 16     909
 19     569
 21     803
 24     414
 26     558
 29     304
 32     226
 34     293
 37     163
 39     230
 42     121
 45     180
 47      89
 40      63
 52     103
 55      62
 57      87
 60      52
 63      35
 65      55
 68      32
 70      62
 73      31
 75      37
 78      21
 81      17
 83      22
 86      16
 88      23
 91      13
 94      15
 96      20
 99       8
101      11
104       9
106      15
109      14
112      10
114      12
117      10
119       9
122       4
125       3
127       6
130       4
132       4
135       2
140       1
143       1
145       1
150       2
163       1
171       2
176       1
181       1
194       1
200       1
202       2
205       1
207       1
210       1
220       1

The hailstone sequence can actually be calculated very quickly with some simple .x86 assembler. The input is put into eax, and ebx counts the number of cycles the number takes to reach 1.

xor ebx, ebx //Start the cycle counter at 0
mov ecx, 3   //Put 3 into ecx for multiplication
Parity:
cmp eax, 1   //Are we done yet?
je Done      //If so, go to the end
mov edx, eax //edx = eax
and edx, 1   //Get parity bit
cmp edx, 0   //Is it even?
je ParEven   //If so, skip straight to that part
//eax is odd here
mul ecx      //treble eax (ecx is just 3)
add eax, 1   //and +1
add ebx, 1   //increment cycle counter
//eax is now even, so flow straight into even handler
ParEven:
shr eax, 1   //divide by two
add ebx, 1   //increment cycle counter
jmp Parity   //time to test parity again
Done:

Just to clarify how this works:

• See if eax is 1 yet. If so, we're done.
• If not, get just the last bit of eax. Note that this determines whether eax is even or odd.
• If it is odd, triple and add one as usual.
• Now eax is certainly even - if it wasn't before, the previous step made it so.
• Half it quickly by shifting all the bits right. This is just like the quick method of dividing by ten in our usual base 10.
• Add one to the cycle counter, and start over.

There are a couple of micro-optimisations, which are allowed since the code is so simple. For example, we xor ecx against itself to set it to 0, rather than using mov. This is just showing off!

Please note this is MSAM. Strictly, we should use jr, in place of jmp with line lables. Likewise, the C-style comments would probably not be approved of but I thought it was more important that the code was understandable.

When I was in high school my AP Computer Science professor presented our class of eleven students with a very interesting algorithm. He called it 3n+1 (it is really the Collatz Conjecture). He claimed that given any positive, non-zero integer when the following steps are applied, the result will always be 1.

n := <any postive non-zero integer>
while (n != 1) do
  if (n is even) then
    n := n / 2
  else
    n := 3 * n + 1
  end if
end while

To a class of nine seniors and two juniors, Mr. Ball gave this algorithm and told us to play with it and see what happened. Did I mention Mr. Ball was a great teacher?

Naturally we went to our respective, half-functioning 386s and 486s loaded with pirated copies of Turbo Pascal 7 and went to work. The faster typers noticed "a problem."

Student: Mr. Ball? I entered ten thousand to test the function and the printout "went negative."

Mr. Ball: So what does that mean?

Student: Well, we've hit MAXINT when calculating 3n+1.

Mr. Ball: mmmhmmm. So what number makes the function overflow?

I did not realize it at the time but he taught us a valuable lesson: Learn what values will cause an overflow. After some Pascal voodoo the class decided that the number was 447¹. I've remembered that number since 1998 as a "stand out" number. (The 47 society is expecting my dues any day.)

Like I said, this is an interesting algorithm and it has been suggested² that this is unprovable. I don't know about that, I'm a programmer, not a mathematician. Maybe some number theory buffs will stop in and clear this whole mess up.

1: For the curious the sequence for 447 goes:
447:1342:671:2014:1007:3022:1511:4534:2267:6802:3401:
10204:5102:2551:7654:3827:11482:5741:17224:8612:4306:
2153:6460:1615:4846:2423:7270:3635:10906:5453:16360:
8180:4090:2045:6136:3068:1534:767:2302:1151:3454:1727:
5182:2591:7774:3887:11662:5831:17494:8747:26424:13121:
39364:19682:9841:29524:14762:7381:22144:11072:5536:2768:
1384:692:346:173:520:260:130:65:196:98:49:148:74:37:112:
56:28:14:7:22:11:34:17:52:26:13:40:20:10:5:16:8:4:2:1 - qed

2: http://arxiv.org/abs/math.GM/0312309 contains a paper which claims "In this paper, we show that any proof of the Collatz $3n+1$ (sic) Conjecture must have an infinite number of lines. Therefore, no formal proof is possible. We also discuss whether the proof strategy in this paper has any promise for proving that the Riemann Hypothesis is also unprovable." -- And it appears that this has been cleared up: cakedamber writes:

"Ok. There's a few reasons that guy is wrong. I'm assuming you read the paper? (It's rather short and the key bit is just a paragraph long.) The problem with his proof is on several counts. First, and simplest, is that you don't need to talk about every last value of a function in order to prove something about that function. If you did, you could never prove anything about ANY infinite-domained function. The second problem is that you don't necessarily need as many words/letters as there are values anyhow. In fact, it's possible to talk about infinite sets using only a finite number of words. On top of that, there are some really deep philosophical paradoxes that pop up if you assume that there's a simple mathematical mapping from functions to natural-language definitions. Those last two are really just the icing on the cake, though -- the first one is more than enough to show that the paper's hogwash."