# 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,1,4,2,1 (loop)**

*2***: 3,10,5,16,8,4,2,1 (loop)**

*3***: 4,2,1 (loop)**

*4***: 5,16,8,4,2,1 (loop)**

*5*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 infinitely2.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
: (3(103)+1)/2 = 155 which is a number that features later in the same*103***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,
? After applying (3x+1)/2, it becomes 161 which is*107***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
follows the sequence 111,334,167,502,251,754,377… 167 is found in the same*111***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,155,233 (233 is*103***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,167,251 (251 is*111***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

**ends there. But looking across to the right, there will always be another number, for example**

*127***: 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**

*255***and**

*127***get eliminated after the 8th deduction (at the red circles), while the Input Integers**

*383***and**

*255***don’t and will go for one or more rounds.**

*511**(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.