On the 3x+1 Problem: An introduction

Right now, I am currently working on a paper related to the 3x+1 Problem, so I thought I would write up a short primer to a truly beautiful theorem involving a truly interesting mathematics problem that almost certainly has no bearing on anyone’s day-to-day life. Unfortunately, it has ended up being a rather large post, so I have decided to split it up in to a few pieces. As I do them, I will add links here.

• Part I: An introduction to 3x+1 (this one)
• Part II: Basic algorithm speedups
• Part III: The Structure Theorem

Wikipedia has a decent primer on the 3x+1 Problem, A.K.A. the Collatz Conjecture. But it's also very easy to state what turns out to be a very difficult problem. Say I tell you to pick any whole number (i.e., an integral number that is 1 or bigger). Now:

• If the number you picked is odd, multiply it by 3, and then add 1 (hence, 3x+1).
• If the number you picked is even, divide it by two.
• Repeat the last two steps until you hit 1.

So that is what you do. Before getting to the conjecture, let’s try a couple of examples.

An easy one is 7. This is odd, so the next step is 22. That is even, and so now we get 11. This is now odd, and we next get 34. Even, so 17. Odd, so 52. Even, so 26. And then 13, 40, 20, 10, 5, 16, 8, 4, 2. Finally, we get 1.

Writing this in a shorter notation, we would write

7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1.

Let’s try a few close-by numbers. Surely they must be similar, right?

6→3→10→5→16→8→4→2→1.

Here we picked just one less, and it was a heck of a lot shorter. So maybe smaller the starting number, the smaller the path? Let’s try another one.

8→4→2→1.

We went one bigger, and it was even shorter. In retrospect, that couldn’t have been right, anyway. Just look at that first sequence. The number 52 is much bigger than 7, but we know its sequence is shorter than 7’s (52’s sequence is the subsequence starting at 52 and then going to 1.) But just to be sure, let’s try one more.

9→28→14→7→…

I stopped there, because after we hit 7, we already know what’s going to happen.

So anyway, what’s the conjecture? At its simplest, the conjecture is every whole number goes to 1. Seems simple enough. And guess what. Remember that number you picked? Well, if I were a betting man, I would bet it did eventually go to 1. In fact, all numbers up to 2^60 have been checked with a computer (for those people who do not regularly work in powers of 2, 2^10 = 1024, so it’s slightly bigger than 1000. That means 2^60 is bigger than 1 billion billion.) It is a safe guess that you didn’t pick a number that high. But the reason we are using computers to manually check is because of one simple fact: nobody knows whether the conjecture is true or not.

Of course, a lot of people have opinions one way or another. Most people would be surprised if it turned out to be false. But the fact of the matter is, 2^60 is peanuts compared to how many whole numbers there are. Actually it’s less than peanuts. Even people involved with homeopathy would probably be distressed with the ratio of numbers checked to all the numbers out there.

So, that’s the 3x+1 Problem. I should point out that just because no one has solved the conjecture does not mean that nothing has been done to study it. A friend of mine did some work on this for his undergraduate thesis 6 years back, and look at the pretty pictures he made.

There is of course the question of why anyone would want to spend time looking at this problem. In my case, I would say to just look at how simple the problem is. If it is even, divide by two. If it is odd, multiply be three and add 1. We are talking about a beautifully simply problem. And we can’t even prove a simple conjecture about it. If we can’t do this, what hope do we have on any harder problems?

Next time, I will talk about ways to (mathematically) speed up calculating if a number eventually goes to 1.

Technorati Tags: mathematics, Collatz+Conjecture