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

Creating some more experiments. Stay tuned…