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 zero, 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 4471. 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 suggested2 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."

Log in or register to write something here or to contact authors.