This holiday season I got caught up on the Veratasim YouTube channel. Unfortunately, this resulted in second-degree burns from the most dangerous problem in mathematics: the Collatz conjecture.
I recommend that you watch the video from the beginning if have not heard of this conjecture before. Derek does a great job explaining it.
In the video, there is a segment just a few seconds long that shows the binary representation of the sequence of numbers as an image generated in matlab. I really like this visualization, and it’s worth exploring a bit deeper.
Another way of stating the conjecture is: if you do the operation $x_{n+1}=3x_n+1$ repeatedly on any number, the nonzero digits will always converge into to a single 1.
There is an intuitive and visual explanation why this statement is (almost?) always true. On the left, the value of the number is written in binary, and on the right I have included the same number, with the value as you would normally see it in the Collatz conjecture.
1 1 | 1048577
11 1 | 786433
1 1 1 | 589825
11 11 1 | 442369
1 1 1 1 | 331777
1111 11 1 | 248833
1 11 11 1 1 | 186625
1 1 1 11 1 | 139969
11 11 1 1 1 | 104977
1 11 111 11 1 | 78733
111 11 1 1 1 1 | 29525
1 1 11 1 | 173
1 1 | 65
11 1 | 49
1 1 1 | 37
111 | 7
1 11 | 11
1 1 | 17
11 1 | 13
1 1 | 5
1 | 1
1 | 1
1 | 1
1 | 1
Let’s make some observations.
- The right edge initially moves left at 4x, and it is already in the equivalent of the 1, 4, 2, 1 loop.
- The left edge of the graph is moving right at a rate of 3x.
- Towards the bottom left of the graph, the edges converge to into the stable and familiar 4x or 1, 4, 2, 1 loop.
- On occasion, the right edge does not always move 4x. If the two least
significant digits on the right are equal to
11in binary, then the right edge will move left only at 2x. Otherwise, it will move left at least 4x, and sometimes much more. - Information can only flow from right to left: Nothing on the left has any effect on the bits to the right. The right, however cascades into the left all the time.
- The significance of the seed 1048577 is completely obfuscated in base-10, but in base-2 we see why it is a special number. We want to initially isolate the dynamics of the left and right edges.
So, why is this not enough to prove the conjecture? If the left side is mostly growing slower than the right side, won’t the edges eventually converge?
I’ll answer that with a different (wider) example.
111111111111111 | 32767
1 11111111111111 | 49151
1 1111111111111 | 73727
11 1 111111111111 | 110591
1 1 11111111111 | 165887
1111 1 1111111111 | 248831
1 11 11 111111111 | 373247
1 1 1 1 11111111 | 559871
11 11 1 1111111 | 839807
1 11 111 1 111111 | 1259711
111 11 1 1 1 11111 | 1889567
1 1 11 1111111 1 1111 | 2834351
1 11 111111 111 | 4251527
11 1 1 1111 1 1 11 | 6377291
1 1 11111 11 1111 1 | 9565937
11 11 1 1111 1 11 1 1 | 7174453
1 1 1 11 1 111 1 | 672605
1111 11 1 1 11 | 252227
1 111 1 1111 1 1 | 378341
1 1 1 1 11 11 | 70939
11 111111 1 1 1 | 106409
1 11 1111 111111 | 79807
111 1 111 11111 | 119711
1 1 1111 1 11 1111 | 179567
1 111 1 111 | 269351
11 1 1 1 111 11 | 404027
1 1 111111 1 11 1 | 606041
11 111 11111 11 | 454531
1 1 11 111 1 1 1 | 681797
11111 11 1 111 1 | 127837
1 111 11 1 11 | 47939
1 11 111 1 1 | 71909
11 1 1 1 1 11 | 13483
1 1111 1 | 20225
111 11 1 1 | 15169
1 11 111 1 | 11377
1 1 1 1 1 1 | 8533
11 1 | 25
1 11 | 19
111 1 | 29
1 11 | 11
1 1 | 17
11 1 | 13
1 1 | 5
1 | 1
1 | 1
1 | 1
We see right away that the number 32767 starts orders of magnitude smaller, but takes more iterations to stabilize. And it is clear why: we seeded it with a solid block of 1’s. Some more observations:
- For the first set of iterations, the right side is growing at 3x as always.
- The left side cannot grow faster than 2x until it gets past that initial block. The edges diverge (and the equivalent number grows) during this time.
- Most importantly: Blocks can form naturally. Halfway down from the top, another block appears right on the edge. Once again, the edges diverge.
If there were some initial seed that could make the two rightmost bits equal to
11 in binary most of the time, the number might escape the conjecture’s
gravity and grow on forever. Anyway, even if we did find it, it could be too
large to send in an email to the elders of math or publish in a Journal.
I hope this demo intuitively explains why the conjecture is true for every number ever tried, but also why it may be impossible to write a proof for it.
Finally, the title of this post is “Collatz’s Game of Life”, this a reference to Conway’s Game of Life. I don’t know the history, but the Veritasium video mentions Conway’s FRACTRAN, and I am sure Conway was aware of the Collatz conjecture. I like to think about the Collatz conjecture as a “game of life”, where all the little bits must interact in the positive 1D space rather than on an infinite 2D plane.