3n + 1

This weekend I gave a middle school version of a keynote lecture at the local Mathcounts tournament, as a group of 5th to 8th graders finished slices of pizza and waited for the contest results to be posted. The talk actually went quite well. It was my first ever powerpoint, and I must admit there is some real power to including video in a presentation.

I talked about the 3n+1 problem, a lovely little unsolved problem that is incredibly simple to relate, but virtually impossible to get anywhere with. It goes like this: say you pick a number, and generate a sequence based on the following two rules:

1. If your number is odd, multiply it by 3 and add 1.

2. If your number is even, divide it by 2.

Then you repeat that process with your new number. So for example, if you start with 5, you get the sequence

5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1 …

and the 4, 2, 1 loop repeats.

Now the absolutely astonishing thing is that no matter what number you start with, you always seem to come back to 1 eventually. But nobody knows if it’s true for ALL numbers, and no one can prove it. Try it… even some simple numbers can take a long time, but they all get to one eventually.

The nature of these unsolved problems, especially when their statement is so simple, makes me want to know their answers. Why does this happen? Does it even happen, for sure, always? I need to know why, why multiplying by 3 and adding 1 has this strange behavior.

Incidentally, I tried multiplying by 3 and subtracting 1 and didn’t get anything like this. Only about 34% of the numbers I tried came back to 1 in that case.

If I chose a and n in some sufficiently random way, and built some an+1 sequence in a sensible manner, what is the chance the sequence generated by those choices would return to 1?

Sometime I feel we don’t even understand how multiplication and addition are truly related, at the deepest level.

And no one can satisfy my desire to know. We live with mysteries.