Skip to content

Attempt the 3x+1 Problem

I was introduced to the \(3x+1\) problem in a few [1] [2] YouTube videos, which made it seem like there was no solution. I am here today to prove them wrong! Or perhaps, right, depending on how you interpret this. As I was writing this, I kind of lost track of what I was doing.

The \(3x+1\) problem goes like this. Start with any number \(x_{0}\).

  • If \(x_{0}\) is odd, then \(x_{1}=3x_{0}+1\)
  • If \(x_{0}\) is even, then \(x_{1}=x_{0} \div 2\)
  • Rinse and repeat! Did you make it to infinity?

For example, if you start with the number \(x_{0}=5\), which is odd, the next number in the sequence is \(x_{1}=3 \times 5 + 1 = 16\) which is even, so the next number is \(x_{2}=8\), then \(x_{3}=4\), then \(x_{4}=2\), then finally \(x_{5}=1\). If you wanted to continue, \(1\) is odd, so the next number in the sequence is \(4\), which we already know goes back to \(2\) and then \(1\) and repeats the same cycle of \(4 \rightarrow 2 \rightarrow 1\).

In the Veritasium video, Derek mentions that mathematicians have tried with brute force, all numbers to about 300 quintillion to see if any number shoots off to infinity, but none were found. I'm here today, or rather in the middle of the night (as usual) to prove them that all that work was useless! Or maybe some of that work, possibly.

I'll start off by defining an even number by \(e=2k\) and an odd number by \(o=2k+1\) where \(k\) is any integer, also knowing these facts:

  • \(e \times e = e\)
  • \(e \times o = e\)
  • \(o \times o = o\)
  • \(e + e = e\)
  • \(e + o = o\)
  • \(o + o = e\)

If \(x_{0}\) is odd, \(x_{1}=3o+1=e\) which means that certainly the second number in the sequence is \(x_{2}=\frac{x_{1}}{2}=\frac{3x_{0}+1}{2}\). Now, an even number divided by another even number might be even or odd. For example, \(\frac{4}{2}\) is even, but \(\frac{6}{2}\) is odd. So, we cannot say whether or not \(x_{2}\) is even or odd, but we can "force" it one way or another using our definitions.

If we want our sequence to keep growing, that means \(x_{2}\) has to be odd. (An even number would just be divided by 2.) So \(x_{2}=2k+1\). Here's what we get if we set those 2 formulas for \(x_{2}\) equal to each other.

\[ \begin{aligned} x_{2} = \frac{3x_{0}+1}{2} &= 2k+1 \\ 3x_{0}+1 &= 4k+2 \\ 3x_{0} &= 4k+1 \\ x_{0} &= \frac{4k+1}{3} \end{aligned} \]

\(k\) has to be an integer, and \(x_{0}\) also has to be an integer, so \(4k+1\) must be divisible by \(3\). I'm not really sure how to prove this mathematically, but it's easy enough by looking at it to know that \(k=3n+2\) where \(n\) is any integer... for real this time. Plugging that in...

\[ x_{0} = \frac{4(3n+2)+1}{3} = \frac{12n+8+1}{3} = \frac{12n+9}{3} = 4n+3 \]

All right, sweet! Now that we have a formula for our starting point, let's try it out.

n=0;k=2;x=3

\[ \begin{aligned} n&=0;k=2;x_{0}=3\\ x_{1} &= 3 \times 3 + 1 = 10 \\ x_{2} &= 10 \div 2 = 5 \\ x_{3} &= 3 \times 5 + 1 = 16 \\ x_{4} &= 16 \div 2 = 8 \\ x_{5} &= 8 \div 2 = 4 \\ x_{6} &= 4 \div 2 = 2 \\ x_{7} &= 2 \div 2 = 1 \\ \end{aligned} \]

...and we're done. But our series increased twice, and we can try a different \(n\) value.

n=1;k=5;x=7

\[ \begin{aligned} n&=1;k=5;x_{0}=7\\ x_{1} &= 3 \times 7 + 1 = 22 \\ x_{2} &= 22 \div 2 = 11 \\ x_{3} &= 3 \times 11 + 1 = 34 \\ x_{4} &= 34 \div 2 = 17 \\ x_{5} &= 3 \times 17 + 1 = 52 \\ x_{6} &= 52 \div 2 = 26 \\ x_{7} &= 26 \div 2 = 13 \\ x_{8} &= 3 \times 13 + 1 = 40 \\ x_{9} &= 40 \div 2 = 20 \\ x_{10} &= 20 \div 2 = 10 \\ x_{11} &= 10 \div 2 = 5 \\ x_{12} &= 3 \times 5 + 1 = 16 \\ \end{aligned} \]

This time our series increased 5 times but we still ended up at a power of 2, so we're done again.

n=2;k=8;x=11

\[ \begin{aligned} n&=2;k=8;x_{0}=11\\ x_{1} &= 3 \times 11 + 1 = 34 \\ \end{aligned} \]

We've already seen this number. We're done again!

n=3;k=11;x=15

\[ \begin{aligned} n&=3;k=11;x_{0}=15\\ x_{1} &= 3 \times 15 + 1 = 46 \\ x_{2} &= 46 \div 2 = 23 \\ x_{3} &= 3 \times 23 + 1 = 70 \\ x_{4} &= 70 \div 2 = 35 \\ x_{5} &= 3 \times 35 + 1 = 106 \\ x_{6} &= 106 \div 2 = 53 \\ x_{7} &= 3 \times 53 + 1 = 160 \\ x_{8 \dots 12} &= 160 \div 2 = \dots = 5 \\ \end{aligned} \]

We've already seen this number as well. Not looking good!

n=4;k=14;x=19

\[ \begin{aligned} n&=4;k=14;x_{0}=19\\ x_{1} &= 3 \times 19 + 1 = 58 \\ x_{2} &= 58 \div 2 = 29 \\ x_{3} &= 3 \times 29 + 1 = 88 \\ x_{4 \dots 7} &= 88 \div 2 = \dots = 11 \\ \end{aligned} \]

Let's press on...

n=5;k=17;x=23

We've already seen \(23\) in the sequence.

n=6;k=20;x=27

Without going through all the math, this one takes 111 steps to get to 1, with 41 increases.

Conclusion

Honestly I thought I figured it out, lying in bed. But I guess all those mathematicians were right, it seems to be unsolvable. With \(n = \infty\) it might work. But at that point you've already reached infinity before you began the process. At least here I was able to narrow it down to \(x_{0}=4n+3\), which is only 25% of all numbers!