Let’s try an experiment. Think of a positive whole number. Any number will do. Now, follow this simple rule: if the number is even, divide it by two. If it’s odd, multiply by 3 and add 1. Repeat this process until your resulting number is 1. So, for example, suppose we start with 5. We multiply by 3 and add 1, to get 16. Then, following the same rule, we divide by 2 to get 8. Then we divide by 2 to get 4, and divide by 2 again to get 2, then 1. If you try this with a few numbers, you’ll see that although you may go up and down a few times, you always seem to end up at 1. But are you always guaranteed to arrive at 1, no matter what number you started with?
Believe it or not, this simple question has not been solved. It’s a famous open problem of mathematics, known as the Collatz Conjecture, or the “3n+1 problem”. If we define the stopping time as the number of steps to get to 1, this conjecture can be stated as follows: all positive whole numbers have a finite Collatz stopping time. Despite being simple enough to explain to an elementary school student, this problem has defied the efforts of mathematicians and hobbyists for nearly a century. The late quirky mathematician Paul Erdos once offered a $500 bounty for anyone who solves this problem, but this vast fortune has not yet been claimed.
By experimenting manually with a few numbers, you can easily convince yourself that the conjecture is true— it seems like you really do always end up back at 1, no matter how you started. Yet your path to get there can vary wildly. If you start with a power of 2, you can see that you’ll dive straight back to 1. Some well-positioned odd numbers are almost as easy: for example, if you start with 85, you’ll then jump to 256, which is a power of 2, and head straight back from there to 1. On the other hand, if you start with the seemingly innocent number of 27, you will find the total stopping time is 111 steps, during with you visit numbers as high as 9232. The Wikipedia page has some nice graphs showing how the stopping time varies: its maximum value seems to slightly increase as the starting numbers increase, but there is no simple pattern that can be established to prove the conjecture. Computers have experimentally shown that the conjecture holds for numbers up to 2^60, but of course that does not prove that it will remain true forever.
This Collatz stopping time function can also be seen as an example of chaos, a case where a very slight change in initial conditions can cause a dramatic difference in the result. Why is it that starting with 26 will enable you to finish in a mere 10 steps, while increasing to 27 takes 111 steps, and then many higher numbers have far fewer steps? It’s a good example to keep in mind when someone claims they have made accurate predictions about some iterative physical system using computer models. Can they make the case that their model is somehow simpler than the Collatz process, of either halving or tripling and incrementing a single number at a time? If not, what makes them think their modeling is less chaotic than the Collatz problem, or that their initial conditions are so accurate that they have ruled out chaos effects?
As with many unsolved problems, this problem is also attractive to many slightly self-deluded amateurs, who every few years publish an article or make an online post claiming to have proven it. One simple way to test any proposed proof is to see if it also applies to very similar problems for which the conjecture is false. For example, instead of multiplying odd numbers by 3, multiply them by 5 before adding 1, turning the question into the “5n+1 problem”. In that case, if we start with the number 13, the sequence is 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13. Since we got back to the number we started with, this means we repeat forever, without ever getting back to 1! Thus, any attempted proof of the Collatz 3n+1 problem would have to also have some built-in reason for why it doesn’t apply to the 5n+1 version. Why is the number 3 so special compared to 5? Well, if I could answer that, I would be riding away in a limo paid for by Erdos’s $500.
Still, even if you don’t expect to solve it, it is kind of fun to play with example values and look for patterns. The way that this simple formula can seem to cause numbers to wander away from you, circle around and tease you temptingly, or race straight down to 1, can seem almost lifelike at times. An intriguing online abstract claims to describe the problem as “an ecological process of competing organisms”, made of 1s in bit strings. (Sadly, the full paper for that one is hidden behind a paywall, so I wasn’t able to read it.) But I think my favorite summary of the problem is the one in the XKCD web comic: “The Collatz Conjecture states that if you pick a number, and if it’s even divide it by two and if it’s odd multiply by three and add one, and you repeat this procedure long enough, eventually your friends will stop calling to see if you want to hang out.”
And this has been your math mutation for today.
References:
- https://www.math.auckland.ac.nz/~king/745/collatz.pdf
- https://en.wikipedia.org/wiki/Collatz_conjecture
- https://xkcd.com/710/
- http://unsolvedproblems.org/index_files/Collatz.htm
- http://www.mitpressjournals.org/doi/pdf/10.1162/artl_c_00024
- http://math.stackexchange.com/questions/14569/the-5n1-problem
No comments:
Post a Comment