Thoughts on the Collatz Conjecture
Years after keeping the handwritten notes in the big pile of doucments on my desk (as a result of my constant procrastination and ADHD — on which I like to blame all my weaknesses), I have finally gotten some time to revisit the thought process and lay out my logic properly somewhere digitally.
I came across this video in August 2021 as I was enjoying my Five Guys takeaway dinner in the office. It was almost 2 years into COVID-19, so I got used to getting takeouts and enjoying them at my desk while watching videos of my favorite car reviews, music videos or engineering and science documentaries (Veritasium, 3Blue1Brown, Steve Mould, etc). That day we were going to the investment committee for the first time since COVID — a late night IC call was scheduled with partners from Europe and the US so I had to stay behind for a few more hours.
At beginning of the video, the host proclaimed in the usual clickbait fashion, “this is the most dangerous problem in mathematics”, and went on to explain the unsolved 3x+1 problem. Why it was fascinating is exactly because it is such a simple conjecture. Growing up, I always loved maths but never took up any real science courses in college in the pursuit of a sexier and high-earning finance career (models and bottles). I realised this was my perfect opportunity to take a short pause from everything pest control (which was what my investee company does). Plus, my mind was already overloaded with all sorts of analyses around: correlation between concentration of operating sites and gross margins, picking the best strategy between increasing density vs. national footprint, pace of add-on acquisitions and its impact on equity check, dilution and IRR..
Anyway, the Collatz Conjecture proposes that for any positive integer, if you apply the following set of rules repeatedly, it will always end up in 1:
1. If the number is even, divide it by 2… operation a
2. If the number is odd, apply 3x+1… operation b
Repeat
As an illustration, the sequence for the numbers 1–5 are as follows:
1: 1,4,2,1 (loop)
2: 2,1,4,2,1 (loop)
3: 3,10,5,16,8,4,2,1 (loop)
4: 4,2,1 (loop)
5: 5,16,8,4,2,1 (loop)
As you’ll notice, the numbers in the sequence may go up or down, depending on how many times operation b (increasing the number), or operation a (reducing the number), is performed. This is why the set of numbers is also called the Hailstone Sequence. Lothar Collatz conjectured that:
However long it may take the numbers in a sequence to rise and fall, it will eventually revert to the 4,2,1 loop (rather than rising forever to infinity)
However, no one appears to have found a valid proof for this problem, despite there is even decent prize money for finding a solution.
On the other hand, if the conjecture is false, one should be able to find either:
1. A number that increases infinitely
2.A number that does not fall down to the 4,2,1 loop, but instead forms another repeated loop x,y,z,x,y,z (loop)
For possibility #1, if such sequence exists, it will not be possible to show it empirically so instead, it would require a theoretical proof. I read that someone has already verified all positive integers up to 10²⁰ and all of them ended up in the 4,2,1 loop (surprise, surprise). Based on this, it was also suggested that for possibility #2, any possible loop ending in x,y,z instead of 4,2,1 would be billions of numbers long.
This is also interesting because with today’s computing power supercharged with AI and degens like me with no better things to do in life, one should’ve easily audited the first quadrillion numbers and beyond. Why has no one found a proof or disproof for the conjecture?
p.s. I’ve found quite a few articles and papers posted online within the past 2 years, probably also inspired by the same Youtube video and the work done by Terence Tao. However I have not found anything more than random papers and Medium articles offering incomplete arguments and illogical deductions.
I’ve decided to do it my own way and write down my observations and try to observe possible patterns. Brute-force arithmetic has also been a favourite strategy for my Math Olympiad problems so I thought I could compute my way out just like the good old days.
Given most smaller integers have already been tested true for the conjecture, I’ve skipped the first 100 numbers (“Input Integers”) in my “mental computer program” and recorded them as “true”.
Starting from the Input Integer 101, given it is an odd number, operation b is performed which results in an even number 304, hence operation a will be performed subsequently to arrive at 152. Then, operation a is repeated to arrive at 76. Because we have already tested all numbers before 100, we know that 76 will eventually revert to the 4,2,1 loop and thus the Input Integer 101 is not the counterexample we’re looking for. The simple observation here is that any odd number will go through (3x+1)/2 or 1.5x+0.5 which lands on a bigger number. Any even number will go through x/2 which becomes a smaller number.
For the Input Integer 102, operation a is performed to arrive at 51. 51 has also been tested “true” for the conjecture.
For 103, similar to 101, it goes through (3x+1)/2 to become 155. But unlike 101, after performing the first two operations (operation b then operation a), the result is still an odd number. Because 155 is a number that comes later in the mental program and has not yet been tested, we cannot put 103 to bed at this point like what we did to 101 and 102. In fact, the sequence that comes after 103 is very long: 155,233,350,175,263,395,593,890… We’ll store this number 103 in our cache memory for now.
For 104, as with all the even numbers that comes after, we’ll set them aside as “true” right away because once you divide it by 2, it becomes a smaller number that has been previously verified.
For 105, similar to 101 and 103, it goes through (3x+1)/2 to become 158, and then 79. Also similar to 101 (but unlike 103), it ended up in an even number after performing the first two operations, so we have applied a total of (3x+1)/2/2 which ended up in a smaller number than the original Input Integer 105. This smaller number has been verified by our mental program earlier.
And so on..
By laying out the first 100 numbers (all tested “true”), as well as the next 10 numbers, we’ve observed the pattern:
- 102 / 104 / 106 and all subsequent even Input Integers will test “true”;
- 101 / 105 / 109 / any other Input Integers x=101+4n will also test “true”;
- 103 / 107 / any other Input Integers x=103+4n will land on a bigger number after (at least) the first 3 operations. We don’t know if the sequence will eventually drop to a smaller (tested) number because my tiny brain is only set to perform 3 consecutive operations at a time. We will flag this set of numbers x=103+4n as the ones that require further investigation.
Writing down the set of special numbers 103 / 107 / 111 / 115…155 / 159 / 163 / 167… (“special set”), I observed that they increase by the magnitude of 4.
We will now apply the 4th operation of (3x+1)/2 to these special numbers above:
- For 103: (3(103)+1)/2 = 155 which is a number that features later in the same special set, i.e. 155 will increase for at least 2 further operations. We’ll mark 103 as an extra special number within the set. 103 will take a few more operations before dropping to a number that we have verified thus far.
- What about the next number in the special set, 107? After applying (3x+1)/2, it becomes 161 which is not a number in the special set. What this means is that 161 will fall to something smaller after 2 operations: 107,161,242,121… so 107 is not interesting to us anymore and it will test “true”.
- The next number 111 follows the sequence 111,334,167,502,251,754,377… 167 is found in the same special set so 111 is an extra special number
We’ve now established that while 103 / 107 / 111 / 115… form a special set of numbers, 103 / 111 / 119 / 127… are extra special because they will reach greater heights the their subsequent operations. The extra special numbers 103, 111, 119, 127 etc grow in +8 steps
If we repeat the same logic on the extra special numbers 103 / 111 / 119 / 127… we can find another subset that is extra extra special:
- 103: 103,155,233 (233 is not in the special set) so it will fall “true”. Note that I’m no longer spelling out the even numbers in the sequence for simplicity
- 111: 111,167,251 (251 is in the special set, i.e. it will become a larger number after 2 operations). 111 is extra extra special..
- … So is 127, 143, 159… These numbers are extra, extra special and they grow in +16 steps
The significance of the number of steps separating each number in the different special sets lies in that the gap size has doubled (+4, +8, +16, etc) each time we take our analysis one more layer down.
You would have recalled that our very first deduction stated that we only need to consider the next odd number and ignore the even ones. Our second deduction further narrows it down to every 4 numbers (only paying attention to x=103+4n). In the next deduction, we track only every 8 numbers (103 / 111 / 119 / 127)… every 16 input numbers (111 / 127 / 143), etc. The further you drill down, we are eliminating half of the numbers that we’ve picked out in the last deduction, and narrowing it down to the 50% remainder which we believe may grow larger (or not, until proven in the deductions to follow).
We can illustrate this interim conclusion graphically:
- Mental program completed for Input Integers 1-175:
- Mental program completed up to 499:
One can observe that just by repeating the elimination process, we will continue to narrow down the numbers in play.
Take Input Integer 127 as an example. After the 8th deduction we’ll realise that 1457 is not part of the original special set, so the story of 127 ends there. But looking across to the right, there will always be another number, for example 255: 255,383,575,863,1295,1943,2915… that will manage to reach a higher amplitude. We’re starting to see a pattern here: the Input Integers 127 and 383 get eliminated after the 8th deduction (at the red circles), while the Input Integers 255 and 511 don’t and will go for one or more rounds. (Eventually, 255 stops after the 47th iteration and 511 stops after the 61st iteration)
As we continue our mental program to analyse larger and large numbers (towards infinity), we can keep eliminating 50% (and eventually all) of the finite numbers, but we’ll never reach one number that goes up forever. Hence, we conclude that all positive integers follow the Collatz Conjecture and will fall down to the 4,2,1 loop. There is no such positive integer that will rise without bound or form a different loop.
What do you think of my thought process? Comment below.
