Chapter 1:
What is the Collatz Conjecture?
The Collatz Conjecture is one of the most famous unsolved math problems in the world.
It is beautiful.
It is haunting.
It is thought to be nearly-impossible to solve.
The Collatz Conjecture is one of the most famous unsolved math problems in the world.
It is beautiful.
It is haunting.
It is thought to be nearly-impossible to solve.
And yet the question being asked by the Conjecture is so simple you could explain it to a 2nd grader. It's a very fun, approachable math problem. Yet its solution has eluded humanity for over 80 years.
The legendary conjecture was invented by a Mr. Lothar Collatz in 1937. Tinkering with numbers one day, he invented the following:
We're going to build a little "Collatz Machine", a function. Call it C(n). Let C(n) operate from the positive integers to the positive integers. Let C(n) be equal to 3n+1, when n is odd, and let C(n) be equal to n/2 when n is even. I imagine Mr Collatz was playing around with this little function on a pad of paper and decided to see what happens if you iterate it over and over repeatedly on a number. Let's try it out for ourselves.
Let's toss the number n = 7 into the Collatz Machine. 7 is odd and so it becomes 7x3+1 = 22. 22 is even, and so it gets divided by two. 22/2 = 11. 11 is odd and so it becomes 11x3+1 = 34. Writing out the progression, one gets:
7 >> 22 >> 11 >> 34 >> 17 >> 52 >> 26 >> 13 >> 40 >> 20 >> 10 >> 5 >> 16 >> 8 >>
4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
etc...
Note that it eventually gets stuck in a loop.
Let's try out a different number and see what result we get. Maybe n = 15:
15 >> 46 >> 23 >> 70 >> 35 >> 106 >> 53 >> 160 >> 80 >> 40 >> 20 >> 10 >> 5 >> 16 >> 8 >> 4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
etc...
Let's try out one more number. How about n = 100:
25 >> 76 >> 38 >> 19 >> 58 >> 29 >> 88 >> 44 >> 22 >> 11 >> 34 >> 17 >> 52 >> 26 >> >> 13 >> 40 >> 20 >> 10 >> 5 >> 16 >> 8 >>
4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
etc...
Armed with a few experimental trials like this, Mr Collatz gently conjectured "Do all positive integers, when placed into the Collatz system, eventually fall down to the 4 >> 2 >> 1 loop?". This is the Collatz Conjecture.
Trying out various numbers, one always gets a result that looks a little like the above. The orbit of various integers through the Collatz system always feels just a little random, it's very hard to spot a pattern. Yet Mr Collatz probably assumed there was some simple Number Theory trick going on, to explain the Collatz system.... that is, until he tried the number n = 27.
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 >>
4 >> 2 >> 1 >>
4 >> 2 >> 1 >>
etc...
What in the world just happened?!? Why did n = 27 unexpectedly take so many steps to fall and blow up to such a large value along the way? (It reaches 9232) What was different about the number 27? This is the first of the deep mysteries of Collatz Space. No human alive has an answer to that simple question.
Welcome, my friends, to the Collatz Wilderness...