Monday, August 8th, I was introduced to the Collatz conjecture from a link on Daring Fireball. That brief article links to a great video by David Eisenbud that does an excellent job of explaining the mathematical problem and the reason it’s interesting. On Tuesday, August 9th, I again saw a link to it from kottke.org, another blog I regularly read.
For those of you who don’t know, I got my Bachelor of Arts in Mathematics from Reed College in Portland, Oregon. The title of my thesis was “Applications of Counting the Number of Solutions to Linear Equations”, so playing with whole numbers has always been an interest of mine. Since graduation (in 1993) I have largely ignored mathematics, instead focusing on computer software development (I refuse to call it a science or engineering, since to my mind it does not meet the criteria for either of those disciplines).
On Thursday, August 11th, I spent the day at home doing nothing but exploring this problem, and this morning I have some ideas I’d like to share. The explanation below assumes you are familiar with the Collatz conjecture. If not, take time to watch the video linked above, or skim the Wikipedia article.
David Eisenbud really gave me everything I needed to reach this idea – at the very end of the video he asks why 3n + 1, why not 3n - 1?
Starting from this question I asked myself, what is the generalized form of this formula? The original formula as given in the video is:
if n even then n → n/2 if n odd then n → (3 × n) + 1
Lets tweak the definition a little. First lets replace the if n odd with a simple else. Now we have:
if n even then n → n/2 else n → (3 × n) + 1
Second, lets replace the test for evenness with something more generic and more computable. How about using the modulo operator. Then we have:
if n modulo 2 equal 0 then n → n/2 else n → (3 × n) + 1
Now I think we are ready for the generic form. I see three constants that can be replaced by variables. There is the divisor, which I will call d. There is the multiplier, which I will call m. Finally, there is the offset, which I will call o. Substituting those variable names gives us:
if n modulo d equals 0 then n → n/d else n → (m × n) + o
Look at the original formula values and how they relate. In the original formula d=2, m=3, and o=1. and if we look at the simplest sequence, starting from 1, we see 1 → 4 → 2 → 1. From this I have three hypotheses.
- Hypothesis One: To make a valid Collatz function it must be the case that
m + o is a power of d. This is driven by the notion that when you get to one, you want to stay at one, and given that 1 modulo d will never be zero, you need (m × 1) + o to be something that is guaranteed to get right back to one. Clearly m + o has to be a power of d.
- Hypothesis Two: For the Collatz function to tend towards one, it must be the case that
m has a greater absolute value than d. This is just probabilities. Adding an offset after a multiplication means you could end up anywhere (in terms of factors). For it to tend downward you need the divisor to be small compared to your multiplier. You want it to be more likely to hit the divisor than to miss it. A larger divisor is less likely to be a factor of n.
- Hypothesis Three: For the Collatz function to work, it must be the case that
d, m, and o are positive numbers. For d and m this is because of how negative numbers can flip sign on multiplication and division, but addition of the offset is always going the same direction. For o the reason to keep it positive is so that there is no chance that (m × n) + o could ever go negative or to zero.
It has been a long time since I have written a proof, and I don’t know that I’m capable anymore of creating a rigorous proof of my hypotheses, but I plan to spend today trying to write some programs to gather empirical evidence to suggest whether my hypotheses are correct or not, then if reality seems to align with theory, I may take a stab at a proof.
I’m a little concerned that this may end up being equivalent to the halting problem, in which case it won’t be provable, but it seems like this is a simpler case that could be provable on its own.