The Collatz conjecture conundrum

Given that a lot of students are attempting to tackle problems beyond the ones we've done in the course, I decided to try one too. The "TryThisProblem"...problem in the problem-solving wiki lured me in with its mysterious name. Let's just say that the innocent-looking problem inside was not what I expected.

Understanding the problem

The problem proposed was simple enough. For all positive integers, consider the following function:

• if n even: f(n) = n/2
• if n odd: f(n) = 3n+1

f(n) can be called recursively; for example, f(f(f(n))). It is clear that if n is odd, then the next recursive call must use the even branch (n/2), because multiplying two odd numbers produce an odd number, and adding 1 to that produces an even number. Of course, halving an even number always produces a natural number > 0, which is either even or odd.

Because too many nested f's are hard to read, the wiki defined the function F(m, n), where m is the number of times that f(n) is recursively called. For example, F(3, 2) = f(f(f(2))).

The claim: For each positive integer n, there is some natural number m such that F(m, n) = 1. That looked simple enough, and it certainly seemed like something that could be simply proved with a flavour of induction once I found some algebraic connection. So I proceeded to finding a pattern.

Devising and carrying out plans

a. Perplexing polynomials

Always write down a few examples. This is always the best first approach for me, because I get a better intuitive understanding of the problem, and any straightforward patterns are often revealed after a few examples.

I chose a couple of even numbers and a couple of numbers and applied f recursively to them. As you can see below, some of them reached 1 quite quickly, while others took a much longer route. I gave up on n = 55, because it seemed like it might take many, many more steps to reach 1. (Or it might not at all!)

• n = 6: 6, 3, 10, 5, 16, 8, 4, 2, 1
• n = 10: 10, 5, 16, 8, 4, 2, 1
• n = 11: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
• n = 53: 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
• n = 55: 55, 166, 83, 250, 125, 376, 188, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, ...?

One thing I noticed was that the sequence of numbers that were obtained from each recursive call formed a series of valleys and peaks. Additionally, there was a maximum value for each sequence, which I've indicated with bold font. Italicized numbers are non-maximum peaks. This suggested that f(n) for different values of n could be represented by a polynomial of a particular degree.

But how would I calculate this? The number of peaks seemed irrelevant to the values of n. So I temporarily abandoned this approach, and tried another one.

b. Motley multiples and puzzling primes

Our approach in this course and CSC165 to math problems involving even and odd values was to write out the values in term of some natural number k, such that the even or odd properties of the values were apparent.

So I did just that and wrote down a few obvious observations:

• For even n, let n = 2k, where k is a natural number and k > 0. Then f(n) = k.
• For odd n, let n = 2k + 1, where k is a natural number and k >= 0. Then f(n) = 3(2k + 1) + 1 = 6k + 4. Thus, we can reach 4 --> 2 --> 1 when k = 0.
• We want to reach 1, but multiplying by 3 and adding 1 certainly isn't going to get us there. So the only way we can get there is to divide by 2.
• The only way we can reach 1 by halving is if n = 2^i, where i is a natural number.

But where to go from there? I wasn't sure. I decided to note down more generally that I wanted 3n+1 = 2^i, for some natural number i. How does one decrease from a number to such a value?

Instead of trying to solve for a more general problem, I decided to go from natural numbers from a more specific set to 3n+1 = 2^i. I noted in my examples above that F(5, 5) = F(14, 11) = F(9, 13) = F(12, 17) = 1. So for some unknown reason, applying f recursively to 5, 11, 13, or 17 will lead to 2^i at some point. Furthermore, these values of n were linked: from n = 11, you get 17, then 13, and then 5, before finally reaching 16 (which obviously decreases to 1).

Now, it seemed like I was getting somewhere. Perhaps there's a pattern in how different odd values were linked! All I had to do was find some more of these values.

Since 3, 5, 11, 13, and 17 are all primes, I had a reason to believe that odd primes were the key to the solution. So I made a chart of the first few odd prime numbers, starting at 3 (if n = 1, we wouldn't need to do more calculations)! For each prime n, I calculated 3n+1, and checked off whether that resulting value could reach a number that leads to 1. This number could either be 2^i, 5(2^i), 11(2^i), 13(2^i), or 17(2^i) (all the values I know so far to be successful).

I did a lot of wishful thinking and thoughtful hoping while I made the following chart:

For most of the prime numbers I tried, the claim held. The sequence of values from the recursive calls always passed through one of the successful values I'd found in my examples. The remaining prime numbers didn't fail; they just seemed to depend on increasingly larger odd primes, which I had not yet calculated. However, it seemed likely that the pattern would also hold for these values.

But what is the pattern? It appeared that there might be a curved diagonal pattern if my table had a column for each prime number too.

Yet, n = 23 went to an odd, non-prime number first (before proceeding to another prime number). So it wasn't the case that all odd prime numbers would lead immediately to another prime number. My hypothetical expanded chart should not be limited then to only odd primes; I might need to add all odd numbers.

At this point, I was getting rather antsy at the amount of time I was spending on this problem. Even though I dearly wanted to spend the rest of the day -- the rest of the week, even -- working on this problem, I did have four exams to write next week.

My friend had also been working on this problem, and she also couldn't find a solution. While I wrote up a short Python program to test the claim (I tested the first thousand natural numbers, and the claim held for all values), my friend searched online for a few hints. It turned out that this problem is none other than the Collatz conjecture, which has not been solved since Lothar Collatz first proposed it in 1937!

I'm slightly disappointed that I know this claim is unprovable right now, because I know that it's highly unlikely that I'll ever find the solution. After all, if heralded mathematicians haven't been able to prove the conjecture, what chance do I have to prove it? At the same time, I know that if I still thought that there was an obtainable solution, I probably wouldn't have gotten as far as I have on studying for my exams next week. The juxtaposition of the problem's simplicity to the elusiveness of the proof is so beautiful. I actually think that this might happen to me over the Christmas break:

(Source: XKCD)

Purportedly, someone has come close to proving the Collatz conjecture last year, but it's still under review. (If you're interested, you can download the draft as a PDF.) The abstract speaks of equations on a 2D plane, which reminds me of the chart I made, and how I observed that there were diagonal lines going across the chart. Of course, my chart was only for odd primes. If I work on the expanded chart this winter break, I'll be sure to write about it here, even though the course will have finished by then.

Today: Arnsburg, Germany
You should've expected this. You really should've. Obviously, we're in Arnsburg, Germany today, the birthplace of Lothar Collatz (1910-1990). He's most famous for the trivial-looking conjecture I tried to solve above, but he also made many other (arguably more important) contributions to the field of mathematics.