The
Collatz conjecture was proposed by the German mathematician
Lothar Collatz in 1937 and remains unsolved. The conjecture is as follows: start with any natural number, divide by 2 if it is even or else multiply it by 3 and add 1. If one takes the resulting number and recycles it as the input a certain number of times, one will eventually have an output of 1. Go ahead and try it with some small numbers (trying this manually with large initial numbers may require
lots and lots of iterations, so choose carefully!).
What draws me to this particular conjecture is the simplicity in understanding it (which is good since, admittedly, I am by no means mathematically inclined). A few months ago, I spent the day reflecting on this conjecture and had a blast just thinking about it. While this is in all likelihood totally meaningless and irrelevant, I thought I'd share what I thought was curiously interesting found by working on the problem backwards.
If you look at the function of the conjecture ("half or triples plus one"), it's apparent that the iteration that yields an output of 1 will always be by halving the number--you can't triple a natural number and add 1 to get 1. Furthermore, it's apparent that for any number that will yield an output of 1 by continuously halving it will be a power of 2 (i.e., 2, 4, 8, 16, 32, etc.). Given this, we can safely say that once the output is ever a power of 2, the function will eventually yield an output of 1.
We know that if we are halving a number that is a power of 2, the resulting number will also be a power of 2. The question, then, is how this function yields an output that is a power of 2 from a number that isn't a power of 2. For this, we look at the "triple plus one" part of the function and how/when it will yield a number that is a power of 2. I began by looking at the first few numbers that are powers of 2 and tried to see if they were derivable by tripling a whole number and adding 1. I saw that, in a sequence of powers of 2, only every other number was derivable by tripling a whole number and adding 1 (e.g., 16=3(
5)+1, 64=3(
21)+1, 256=3(
85)+1, etc.). The resulting numbers were all powers of 4--probably irrelevant but interesting, or at least I thought so.
I then decided to look at these numbers that yield a number that is a power of 4 by tripling and adding 1 to: 5, 21, 85, etc. While this is probably a big stretch, I decided to see what these numbers looked like in their binary form, as I felt that the "power of 2" element was related to how numbers are represented in binary form (see
this Wiki page on numerical representations in binary). Here's a short list of the numbers that, by tripling and adding 1 to, will yield a number that is a power of 4 in both their decimal and binary representations:
| Dec | Binary | Binary after 3x+1 |
| 1 | 1 | 100 |
| 5 | 101 | 10000 |
| 21 | 10101 | 1000000 |
| 85 | 1010101 | 100000000 |
| 341 | 101010101 | 10000000000 |
And this pattern continues which I thought was interesting. What the pattern reveals is that, if one continues the sequence in the table above, the following number is always the preceding number plus the next power of 4 in the binary. Perhaps that last statement isn't too clear and so I'll try to illustrate my point here:
In binary, "101" can be translated into decimal as "4+0+1", and "10101" as "16+0+4+0+1", and so on. So, 341, which in binary is 101010101, can be translated into
"256+0+64+0+16+0+4+0+1". [Green text will represent 341]. The next number in the sequence will be, then, be the translated "...0+1" with "[next power of 4]+" inserted into the beginning (e.g., 1365 in binary is 10101010101 which can be translated as
"1024+0+256+0+64+0+16+0+4+0+1", or simply the translated binary of 341 with "the next power of four" added to it--that is, 256*4=1024).
If I remember correctly, a cursory glance at this showed me that
only the numbers in the sequence outlined in the table above will yield a number that is a power of 4 by tripling and adding 1. I stopped thinking about the problem here mainly because I got tired but I recall tinkering a bit with division, multiplication, and addition in binary and not being able to find a significant pattern.
Of course, the difficult part of this conjecture is how understanding even numbers that are not powers of 2 eventually yield a number that is a power of 4 by the "halve or triple plus one" function as a whole, and not just by considering either part of the function independently. Also, resorting to binary was probably totally unnecessary, but being not at all mathematically adept, it helped me to better think in a domain of base 2.
