Contemplating the Collatz conjecture (3n+1)

After reading a thread about it, I recently gave some more thought to the Collatz conjecture. According to Wikipedia Paul ErdÅ‘s said about it that “Mathematics may not be ready for such problems.” and professor of mathematics Jeffrey Lagarias is quoted as saying “this is an extraordinarily difficult problem, completely out of reach of present day mathematics.”

It is one of those simple questions which you don’t have to be a mathematician to understand: given any number, if it is even, divide it by 2, if it is odd, multiply by 3 and add 1. Rinse and repeat. The conjecture says that eventually, even though it might be a long and winding road, you will eventually get to the number 1.

Some relevant and interesting links are the Wikipedia article about it and examples of some numbers which travel long paths on the number line before ending up at 1

After this introduction, it’s obvious that my background in mathematics gives me practically a zero probability to prove the conjecture, however I think there’s an intuitive way to understand why it should probably be the case. There’s a flaw in this illustration which will be described, but despite that, perhaps this might give a competent mathematician another avenue to explore for a proof (and perhaps not…) Anyway, comments and criticisms are welcome:

1) The first thing to notice is that dividing an arbitrary even number by 2 has a probability of 0.5 to result in being an even number and a probability of 0.5 to result in being an odd number.

2) The second thing to notice is that 3n+1 will always be even, which means that after arriving at an odd number, we can skip past the 3n+1 calculation step and proceed directly to calculate the number following it in the sequence which will be (3n+1)/2, or 1.5n+0.5

Now combining points 1) and 2) we get that for any given number, there can be two options for the next number in the sequence:
a) with a probability of 0.5, it is even, and then we divide it by 2 to get to the next number in the sequence
b) with a probability of 0.5 it is odd, and then we multiply it by 1.5 and add 0.5 to get to the next number in the sequence

Here is the flaw: Once the sequence generation has started, it can’t be claimed that the following probabilities for an odd/even result for every new number will remain 0.5 anymore since the new number is not generated by a random process, – perhaps a good mathematician might be able to shed light on this. And yet, here’s a result showing the ratio of even vs odd numbers for sequences that start with numbers that take the longest path to get to 1 (taken from here):

The number to start from Number of steps needed (using 1.5n+0.5) Ratio of even numbers in the sequence Ratio of odd numbers in the sequence
279731455495736617 250 0.52 0.48
209798591621802462 248 0.52 0.48
104899295810901231 247 0.51 0.49
93571393692802302 131 0.64 0.36
46785696846401151 130 0.64 0.36
45404032640947650 279 0.49 0.51
22702016320473825 278 0.49 0.51
17026512240355369 322 0.48 0.52
12769884180266527 320 0.47 0.53
7579309213675935 343 0.47 0.53
6482291402296969 327 0.47 0.53
4861718551722727 325 0.47 0.53
4320515538764287 320 0.47 0.53
3586720916237671 250 0.50 0.50
2978729873866753 188 0.54 0.46
2234047405400065 186 0.54 0.46
1675535554050049 184 0.54 0.46
1256651665537537 182 0.54 0.46
942488749153153 180 0.54 0.46
706866561864865 178 0.54 0.46
530149921398649 176 0.55 0.45
397612441048987 174 0.55 0.45
223656998090055 170 0.55 0.45
134345724286089 155 0.56 0.44
100759293214567 153 0.56 0.44
80867137596217 308 0.46 0.54
60650353197163 306 0.46 0.54
51173735510107 301 0.47 0.53
48575069253735 293 0.47 0.53
38903934249727 280 0.47 0.53
27667550250351 354 0.45 0.55
26262557464201 346 0.45 0.55
19536224150271 325 0.46 0.54
14022512981985 334 0.45 0.55
10516884736489 332 0.45 0.55
7887663552367 330 0.45 0.55
7487118137598 322 0.45 0.55
3743559068799 321 0.45 0.55
3700892032993 256 0.47 0.53
2775669024745 254 0.47 0.53
2081751768559 252 0.47 0.53
1899148184679 881 0.40 0.60
1444338092271 879 0.40 0.60
1122382791663 847 0.40 0.60
989345275647 842 0.40 0.60
881715740415 834 0.40 0.60
674190078379 832 0.40 0.60
568847878633 827 0.40 0.60
426635908975 825 0.40 0.60
404970804222 817 0.40 0.60
202485402111 816 0.40 0.60
166763117679 784 0.40 0.60
158294678119 776 0.40 0.60
133561134663 771 0.40 0.60
75128138247 767 0.40 0.60
63389366646 762 0.40 0.60
31694683323 761 0.40 0.60
17828259369 757 0.40 0.60
13371194527 755 0.40 0.60
12235060455 739 0.40 0.60
12212032815 720 0.40 0.60
9780657630 707 0.40 0.60
4890328815 706 0.40 0.60
4578853915 679 0.40 0.60
2610744987 656 0.40 0.60
1674652263 630 0.40 0.60
1412987847 625 0.40 0.60
1341234558 617 0.40 0.60
670617279 616 0.40 0.60
537099606 603 0.40 0.60
268549803 602 0.40 0.60
226588897 597 0.40 0.60
169941673 595 0.40 0.60
127456254 593 0.40 0.60
63728127 592 0.40 0.60
36791535 466 0.40 0.60
31466382 442 0.40 0.60
15733191 441 0.40 0.60
14934241 433 0.40 0.60
11200681 431 0.40 0.60
8400511 429 0.40 0.60
6649279 416 0.40 0.60
5649499 384 0.41 0.59
3732423 374 0.41 0.59
3542887 366 0.41 0.59
3064033 353 0.41 0.59
2298025 351 0.41 0.59
1723519 349 0.41 0.59
1501353 333 0.41 0.59
1117065 331 0.41 0.59
837799 329 0.41 0.59
626331 319 0.41 0.59
511935 295 0.41 0.59
410011 282 0.41 0.59
230631 278 0.41 0.59
216367 243 0.42 0.58
156159 241 0.41 0.59
142587 236 0.42 0.58
106239 223 0.42 0.58
77031 221 0.42 0.58
52527 214 0.42 0.58
35655 204 0.42 0.58
34239 196 0.42 0.58
26623 194 0.42 0.58
23529 178 0.42 0.58
17647 176 0.42 0.58
13255 174 0.42 0.58
10971 169 0.42 0.58
6171 165 0.42 0.58
3711 150 0.42 0.58
2919 137 0.42 0.58
2463 132 0.42 0.58
2223 116 0.43 0.57
1161 115 0.43 0.57
871 113 0.42 0.58
703 108 0.43 0.57
649 92 0.43 0.57
327 91 0.43 0.57
313 83 0.43 0.57
231 81 0.43 0.57
171 79 0.43 0.57
129 77 0.43 0.57
97 75 0.43 0.57
73 73 0.42 0.58
54 71 0.42 0.58
27 70 0.41 0.59
25 16 0.56 0.44
18 14 0.57 0.43
9 13 0.54 0.46
7 11 0.55 0.45

Now lets just assume for now that the probabilities for the next number in the sequence to be even or odd are 0.5. If it isn’t already clear why a succession of such actions should eventually result in descending down to 1, let’s play a game by putting some money on the table…

The game proceeds as follows: You put $100 on the table, and I start flipping a coin. Every time the coin turns out heads, I take half of the money on the table (i.e the total you have left is divided by 2). Every time it turns out to be tails, your money is multiplied by 1.5 (plus a 50 cents bonus). It’s obvious that this game is totally rigged to my advantage as the amount of heads will converge to be similar to the amount of tails, but the loss you incur with each head result (money divided by 2) is larger than the win gained with each tail result (money multiplied by 1.5 + change). Sure, you might make some good winnings, and there will be ups and downs, but the longer the game is played, the more money you eventually lose, until you are left with $1…

The following Python script is a simulation of this process, followed by an example run starting with $100

import random
x = 100
while x > 1:
    print(x)
    r = random.choice([0,1])
    if r==0:
        x /= 2
    else:
        x = 1.5*x + 0.5

Example output

100
50.0
75.5
113.75
171.125
85.5625
128.84375
193.765625
291.1484375
437.22265625
656.333984375
328.1669921875
492.75048828125
739.625732421875
1109.9385986328125
1665.4078979492188
2498.611846923828
3748.417770385742
1874.208885192871
2811.8133277893066
4218.21999168396
2109.10999584198
1054.55499792099
527.277498960495
263.6387494802475
395.95812422037125
594.4371863305569
297.21859316527843
446.32788974791765
223.16394487395883
335.24591731093824
167.62295865546912
83.81147932773456
41.90573966386728
20.95286983193364
31.92930474790046
48.39395712185069
24.196978560925345
36.79546784138802
55.693201762082026
27.846600881041013
42.26990132156152
21.13495066078076
10.56747533039038
16.35121299558557
8.175606497792785
12.763409746689177
6.381704873344589
3.1908524366722943
5.2862786550084415
2.6431393275042208
1.3215696637521104
2.4823544956281656
4.223531743442249
6.835297615163373
3.4176488075816867
5.62647321137253
2.813236605686265
1.4066183028431325

One Comment

Leave a Reply

Your email address will not be published. Required fields are marked *