I have been fascinated by the Collatz conjecture for years. It’s a math problem that is so simple to understand, yet no mathematician has managed to solve it. Since the problem was first proposed by Lothar Collatz in 1937, many mathematicians have gone crazy trying to solve it. Here’s how it works.
The Collatz function takes one number, denoted by n, and turns it into another number. If n is even, the result is n/2. If n is odd, the result is 3n+1. For example, if n is 3 then the result is 10. If n is 4 then the result is 2. If n is 5 then the result is 16. You get the idea.
A Collatz sequence is formed by starting with a number, and repeatedly applying the Collatz function to extend the sequence. For example, the Collatz sequence for n=3 is 3-10-5-16-8-4-2-1. The Collatz sequence for n=5 is 5-16-8-4-2-1. The Collatz sequence for n=2 is just 2-1. Here is a picture of the sequences for n=7 and n=19.
After looking at some of these sequences, you may start to notice a pattern. No matter how high they go, they always seem to come back down to 1. Does every Collatz sequence always come back down to 1? Perhaps some of them get into a loop and keep going round forever, or perhaps some of them just keep going up and up towards infinity. This is the Collatz conjecture: prove that every Collatz sequence eventually comes back down to 1.
Another way to picture the problem is using total stopping times. The total stopping time of a number is the number of steps it takes for the number’s sequence to reach 1. The Collatz conjecture states that every number has a finite stopping time. Despite being such a simple problem, and being open for almost 75 years, nobody has managed to prove or disprove the Collatz conjecture.
There are a couple really tantalizing patterns in the total stopping times. Let me show you just one. Have a look at the first 1000 stopping times.
The first 100 total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.
Notice any patterns? It looks like some of the points are bunching up into short horizontal lines. Furthermore, these short horizontal lines seem to line up in large sweeping curves. To investigate these patterns further, I wrote a short C++ program to draw the same chart, except for the first ONE BILLION stopping times. This time, the x-axis is logarithmic.
The first one-billion total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.
Whoa, now that’s a pattern! Look at all those nice straight lines. Check out a closeup of the bottom-right part of that image.
Close-up of the patterns in the total stopping times
What is causing all those straight lines? Why are they all the same length? The most interesting question to me is, why is there always a long “dash” followed by a short “dot”? If we can explain the structure of these regular patterns, can we construct an exact probability distribution for the total stopping time of any number? Could this distribution be the key to finally proving or disproving the Collatz conjecture? If you want to do a bit of work on the Collatz conjecture, answering these questions might be a good place to start.
Tags: collatz, math, mathematics, pattern, sequence, statistics
Very nice post, Jeff. Now I have another thing to ponder this weekend
Typo: In the second paragraph, you have “odd” and “even” interchanged.
Thanks Jesse! I fixed this now.
From wikipedia:
In 1977 R. Steiner and 2000 and 2002 J. Simons and B. deWeger (based on
Steiner) proved the nonexistence of certain types of cycles.
[...] The Collatz Conjecture—an intriguing example of how graphically plotting data can sometimes lead you to more easily recognize patterns in the data. [...]
Speaking of probability distributions. The rule for odd numbers increases the value of the next number, but also ensures that the next number is even. The rule for even numbers decreases the next number, which could either be even or odd. As a result, the chance of getting an even number as the result of an applied rule is greater than the chance of getting an odd number, which drives the sequence down towards one.
Never mind, I’m wrong, although you could do a probability assessment, its not as easy as I made it out to be, and just shows that the result will diverge, not that it will go one direction or the other.
What’s interesting is if you extend the Collatz function to the complex plane and plot the number of iterations required before convergence; it turns out to be a fractal (the so-called Collatz fractal) which I did a paper on in high school. (See http://www.nathanieljohnston.com/index.php/2009/06/the-collatz-conjecture-as-a-fractal/). Cool stuff.
Sorry, http://www.nathanieljohnston.com/index.php/2009/06/the-collatz-conjecture-as-a-fractal/
Very cool,
I worked on the Collatz Conjectue for my final year project at Uni (Developed a Distributed Computing approach (think SETI@Home) to number crunch) – you should check out the work done by: Eric Roosendaal and Tomás Oliveira e Silva.
Some obversations:
1) every odd number always immediately becomes an even number
2) even numbers are repeatedly divided by two. This will always end in a PRIME number.
Is 2) a proven fact? I’m not a mathimatician!
You divide even numbers by two. If they are again an even number, you repeat this over and over again. This seems to always end in a prime number.
Is that something that is proven? It might be crucial here. Since it was proven, then all you need to prove is that it will go to 1 for all prime numbers.
Oops, I submitted too early!
And my claim isn’t true either. I found a counter example.
But they do seem to converge to prime numbers.
What’s going on?
This is equivalent to proving that eventually a number in the sequence will be a power of two.
interesting to see how primes are mapped on this in red. I like the moire like effect…. intriguing.
I made a silly experiment using the conjecture to generate music. See:
http://wiki.freaks-unidos.net/weblogs/arhuaco/listen-to-the-collatz-conjecture
[...] The Collatz Conjecture « Jeff Cameron’s Blog (jpcameron.com) – February 27, 2010 [...]
You have toooooooooo muuuuuuuuuch time on your hands. Go OUTSIDE! It’s a nice day.
Looks like Randall got in your head already: http://xkcd.com/710/
[...] The Collatz Conjecture « Jeff Cameron's BlogI have been fascinated by the Collatz conjecture for years. It’s a math problem that is so simple to understand, yet no mathematician has managed to solve it. Since the problem was first proposed by Lothar Collatz in 1937, … Read more [...]
Hint,Try subing in 0.999999 instead of one in 3n+1, use 3n+0.999999999.