Image made using photo from Wikipedia
Nina: Nana, have you heard of the Collatz conjecture?
Nana: No. But can I conjecture that you’ll disappear in 5 seconds?
Nina: Sure you can, but it looks like it didn’t work. The Collatz conjecture is a lot more successful. Although, it hasn’t either been proved or disproved for over 8 decades. It’s an unsolved open problem in mathematics.
Nana: I have an unsolved and open problem too. I could give a reward to anyone who solved it.
Nina: You do? What’s it Nana? Is it as interesting as the Collatz conjecture?
Nana: Certainly, and far more important. My problem is how to stop you from talking.
Nina: Pooh! Good luck Nana. No reward is as satisfying as your reactions to our conversations. So as I was telling you, I found out about the Collatz conjecture from a 9 year old girl’s blog post.
Nana: I thought you said it’s an open and unsolved problem in mathematics. Don’t tell me a 9 year old solved it!
Nina: No, she didn’t, but she had loads of fun analyzing it for different numbers and writing up the code for a Collatz calculator. That’s a program that generates the numbers in a Collatz series for any given starting number. Collatz calculators are available on the internet, but she made her own.
Nana: Yuck. She sounds just like you. I pity her grandpa.
Nina: Not every grandpa is a sourpuss like you, you know.
Nana: Really? No way.
Nina: Way! Anyway, so this Collatz problem: the idea is so simple, even you could understand it.
Nana: Hey, watch it young lady. Are you implying I’m not smart?
Nina: Of course not, Nana. I just mean the problem seems so simple, some mathematicians get trapped in it and spend all their lives trying to solve it. That’s why it’s considered a dangerous problem. It’s very deceptive and alluring like a siren.
Nana: Dangerous eh? These mathematicians sure know how to live on the edge. Hyuk, hyuk. Okay come on, lay it on me. Let’s see how it’s so dangerous.
Nina: The idea is, you start with any number. If it’s even you divide it by two, and if it’s odd you multiply it by 3 and add 1. Then you repeat the process with whatever result you get. Collatz conjectured, that if the process is repeated a sufficient number of times, the no matter what the starting number, eventually the series would always result in the number 1, and then get stuck in an infinitely repeating loop of 1 – 4 – 2 – 1.
Nana: You lost me.
Nina: Okay, let me explain with an explain with an example. Say you start with the number 5. It’s odd, so you multiply by 3 and add 1, and you get 16. Now 16 is even, so you divide by 2 and get 8. 8 is even so once again you divide by 2 and get 4 and then 2 and then 1. So in this case you reach 1. But 1 is odd, and so you multiply it by 3 and add 1 and get 4. 4 is even, so divide it by 2 and get 2. Again divide by 2, and you’re back at 1 and the cycle continues forever.
Nana: Sounds like a silly trick. So what’s the big deal?
Nina: I know there are many such fun math tricks, but most of them have simple proofs. What Collatz conjectured was that no matter which number one started with, one would always reach one.
Nana: So let’s see ... If you begin with 12, it’s even and you get 6, and then that’s even too so next you get 3. Oops so that's odd and next you get 10. Hmm. I see this is getting tricky. Well next you get 5. Oh no, that’s odd again and you get 16. Wait, that’s a power of 2, and once you reach that you are bound to reach 1, aren’t you?
Nina: Very good indeed, Nana.
Nana: Okay so that’s easy. All you need to reach is a power of two. For the number 12 it took only 10 steps.
Nina: Sure but did you know that for 27 it takes 111 steps and in the process, for this particular case, the highest number in the series is 9232. That’s what the 9 year old blogger found. She also found that numbers, 25, 26, 28 and 29 all converge in 23 or less steps. So 27 is very strange for no particular reason.
Nana: What? That’s crazy!! Let me try. <10 minutes later> No, no no. I’m not going to get sucked into this. Anyway, even if it is a tedious calculation, it’s easy to follow the steps. So what’s the big deal with the problem?
Nina: The real problem is that no one has been able to prove or disprove the conjecture. Although it has been tested to be true for enormously large numbers, it has not been proved in general. No one knows if there exists an untested exception, which will not reach one when the algorithm is applied to it.
Nana: So in 80 years no one has made any progress on the problem? Shame.
Nina: I never said that. In fact, the reason the girl wrote about it, is because she came across an article about a recent breakthrough in proving the conjecture.
Nana: What does that mean? What breakthrough. Either someone proved the conjecture or they did not, right? What’s the ambiguity?
Nina: Apparently, a mathematician named Terence Tao, proved that when the algorithm is applied to over 99% of numbers the series eventually reaches quite close to one. Although it still does not prove or disprove the conjecture, it is a significant advancement over previously existing attempts.
Nana: I’d settle for getting you to shut up for over 99% of times. It would be quite a win. I see why it’s such a significant result.
Nina: Oh dream on, Nana.
This post is a part of the #NinaAndNana series I co-host with Lavanya Srinivasan. Her posts can be found here.