In this week’s Occupy Math we look at a math problem that can be explained in less than ten minutes — that still stumps every mathematician who has ever looked at it. This problem is also a marvelous place for students to explore and look for patterns (some problems for students are near the end of the post). The problem is based on this rule: “If a number is odd, triple it and add one, but if it is even, divide it in half”. Not a hard rule, but it is the basis of an unsolved problem: “if you start with any positive whole number, do you eventually get to the number 1?” This question has several names. One of the most used is the Collatz conjecture (follow the link for many other names including the very common “3n+1 problem”). A number of prominent mathematicians, including the incredible Paul Erdős, have expressed the opinion that this problem is too hard for us in our current mathematical infancy. The theory also floated briefly, after multiple math departments were consumed by this problem, that it was created by the KGB (the Soviet Union’s spy agency) to stymie mathematics research in the west.
How can such a simple problem be so incredibly hard?
Let’s start with a few examples. We are interested in ending up at one so let’s start there and see if we end up at one:
1→4→2→1
so, yes. There is a cycle 1-4-2-1 that, if the conjecture is correct, is where every other number ends up if you keep repeating the process. Let’s try starting with 3 and see where we go:
3→10→5→16→8→4→2→1
and we see the conjecture works for five. There is also another important issue here — 16 is a power of two and, once we hit one of those, we get a whole chain of even numbers and the value collapses. What happens when you get a number that’s divisible by two several times is probably key to solving the conjecture. Since odd numbers get tripled and even ones only get divided in half it might seem like numbers should, on average, grow. The huge collapse starting at 16 shows why this isn’t the case. It also took eight steps to get from 3 to 1, so the process created by this rule jumps around a whole lot. To give you a notion of how bad this gets, let’s look at the criminal mastermind of small numbers for the Collatz conjecture: 27. Brace yourself.
27→ 82→ 41→ 124→ 62→ 31→ 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→ 790→ 395→ 1186→ 593→ 1780→ 890→ 445→ 1336→ 668→ 334→ 167→ 502→ 251→ 754→ 377→ 1132→ 566→ 283→ 850→ 425→ 1276→ 638→ 319→ 958→ 479→ 1438→ 719→ 2158→ 1079→ 3238→ 1619→ 4858→ 2429→ 7288→ 3644→ 1822→ 911→ 2734→ 1367→ 4102→ 2051→ 6154→ 3077→ 9232→ 4616→ 2308→ 1154→ 577→ 1732→ 866→ 433→ 1300→ 650→ 325→ 976→ 488→ 244→ 122→ 61→ 184→ 92→ 46→ 23→ 70→ 35→ 106→ 53→ 160→ 80→ 40→ 20→ 10→ 5→ 16→ 8→ 4→ 2→ 1
Yowza! That took 112 steps!
It is actually a while before we get an odd number with a Collatz chain much longer than 27 — getting longer even numbers is easy, just double 27 for example — but that’s not too interesting. Let’s look at the conjecture from another point of view. For each number, there is the question, “what number is before this one under the Collatz rule?” Every number must come from an even number — to figure out which number will give N when you apply the Collatz rule, just use two times N. So, for example, 5 comes from 10. Only some numbers are the result of applying the Collatz rule to an odd number — for example 16 comes from 5 but no odd number goes to 12 — and the process of figuring out which ones is probably an important part of attacking the conjecture. Here is a diagram of the numbers eleven or fewer steps from 1.
This diagram (which, in math, is called a tree) is easy to extend and it is a good place to look for patterns. A lot of the patterns hold for a while. Notice, for example, in the above tree that (if we ignore the weirdness of the loop including 1) that every other level of the tree has no two-way branches. That pattern doesn’t hold higher up the tree. This is the wonder of the Collatz conjecture — it is a simple, deterministic rule that gives rise to incredible complexity. Here is another interesting factoid. Since a multiple of three can never be of the form three times another number plus one (the “plus one” screws it up) the chain in the picture that goes from 48 to 3 is going to keep going up forever without branching. Weird, huh? The chain in the tree that is made of powers of 2 branches every other step. See the student problems for more wild speculation about patterns in this tree.
A tool for playing with the Collatz rule
One barrier to exploration of this problem is that the arithmetic can get out of hand. An easy way to the Collatz calculations is with a spreadsheet like Excel or Libre Office. If you put the number you want to start with in cell A1, then the “IF” and “ISEVEN” functions let you build the rule for the Collatz conjecture like this:
IF(ISEVEN(A1),A1/2,A1*3+1)
You then copy the formula down the column to apply the formula over and over until you see a 1.
Some Problems for students.
- This is a really simple one. Show that when you apply the rule for the Collatz conjecture to an odd number you must get an even number.
- The number 27 takes 112 steps to get to 1. Since even numbers always take more steps than the number they go to, can you solve the more interesting problem of finding the smallest odd number that takes more steps than 27 to get to 1?
- Make a chart of how long the numbers from 1 to 100 take to get to 1. See any patterns?
- If a chain is a sequence of numbers that follow the Collatz rule, can you show the chain going up from a multiple of three never branches again?
- An important chain for this problem is 1←2←4←8←16←32←(and all the other powers of 2). Occupy Math said that this chain branches at every other step — can you explain why?
- The tree diagram above shows that every other level has no branches at all (if you ignore the loop at 1), but Occupy Math said that this pattern breaks down. Can you find the first place that it breaks down?
- Explain why the numbers where the tree branches are all even.
- Here is a convenient fact. A number is divisible by three if and only if the sum of its digits is also divisible by three. So, for example 117 is divisible by three because 1+1+7=9 is divisible by three. Can you turn this into a quick test to tell if the tree diagram branches at a given number?
- What happens if you start with a negative number?
- The Collatz conjecture is called the “3n+1” problem because part of the rule is to triple odd numbers and add one. Make up your own rules for generating a sequence of this type and explore what they do. Look for uncontrolled growth, cycles longer than 1-4-2-1, or make your own definition of interesting behavior.
- What rules generates the cycle:13→66 →33 →166 →83 →416 →208 →104 →52 →26 →13 ?
- Based on what you’ve learned, come up with your own pattern for the Collatz conjecture and see if it holds.
More about the Collatz conjecture.
Numberphile is an excellent YouTube channel and they’ve done some videos on the Collatz conjecture. The first one is somewhat artistic and Occupy Math thinks it’s excellent.
If you are mathematically inclined there is even a book about the Collatz conjecture.
The Collatz conjecture is an example of what mathematicians call an unsolved problem. There are a number of unsolved problems — including the Collatz conjecture — that have prize money attached to them. The Collatz conjecture is worth one thousand pounds sterling (from Professor Sir Bryan Thwaithes of Milnthorpe) if you solve it. In addition to trying to entertain you, Occupy Math is taking a chance that one of you might have a valuable insight. This problem has stumped the professionals — there is a small but real chance someone who is not a mathematical professional will find something we missed.
For Occupy Math the big deal is that such a simple rule creates such havoc. An earlier post in this series talked about A Law of the Multiverse and the point was that mathematics exists on its own, separate from minor matters like the laws of physics or which universe you live in. This universality is a beautiful thing: the Collatz conjecture is an example of how little this remarkable universality buys us. Mathematics contains endless wonder and, at present, most of it is beyond us. We need help so if you are mathematically inclined or talented, Occupy Math urges you to continue learning! Do you know of any other killer problems like the Collatz conjecture? Share by commenting or tweeting!
I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics
Occupy Math 