3x+1
Concerning the above math problem, Paul Erdös said that “Mathematics is not yet ripe for such questions.” He also offered $500 USD for its solution. Jeffrey Lagarias said in 2010 that this math problem: “Is an extraordinarily difficult problem, completely out of reach of present day mathematics.” Richard Guy has this on his list of “Don’t try to solve these problems.”
What is the simplest equation no one can solve?
3x+1 popularly called the Collatz conjecture is the simplest math problem no one can solve. Even though it’s easy for almost anyone to understand it’s also at the same time impossible to solve. It’s was named after Lothar Collatz in 1973. This problem has many origin stories and many names. It’s also known as the Ulam conjecture, Kakutani’s problem, Thwaites conjecture, Hasse’s algorithm, the Syracuse problem, and simply 3N+1.
This is the most dangerous problem in mathematics, one that young mathematicians are warned not to waste their time on. It’s a simple conjecture that not even the world’s best mathematicians have been able to solve. This math problem is both famous and infamous as no respectable mathematician is still trying to find a solution for it. It’s thought to be unsolvable.
The Collatz conjecture is the most famous unsolved problem in all of mathematics. This conjecture asks whether repeating two simple arithmetic operations will at some point transform every positive integer into 1. It uses sequences of integers in which each number (or term) is obtained from the previous number as follows: if the previous number is even, the next number is one half of the previous number. If the previous number is odd, the next number is 3 times the previous number plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.
Consider the following operation on an arbitrary positive integer:
If the number is even, divide it by two.
If the number is odd, triple it and add one.
Now form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.
The Collatz conjecture is that this process will eventually reach the number 1, regardless of which positive integer is chosen to start with.
We apply two rules.
If the number is odd, we multiply by three and add one.
So three times seven is 21, plus one is 22.
If the number is even, we divide by two.
So 22 divided by two is 11.
Now, we keep applying these two rules.
11 is odd, so we multiply by 3, 33, and add 1, 34.
Even, divide by two, 17, odd.
Multiply by 3, 51, add 1, 52, even.
Divide by two, 26, still even.
Divide by two, 13, odd.
So we multiply by 3, 39, add one, and that’s 40,
which is even, so we divide by two, 20,
divide by two, 10, divide by two, five, odd.
Multiply by three, 15, add one, 16, divide by two that’s eight, and then four, two, and one.
Now, one is odd, so we multiply by three and add one,
which equals four.
But four goes to two, goes to one,
so we’re in a loop, and the lowest number is one.
Now, the conjecture is this: every positive integer, if you apply these rules, will eventually end up in the four, two, one loop. [1]
The two things that are so fascinating about this math problem is that you can start with any number and take it through the iterations and you will get wildly different pathways for each number as some can go very high before getting trapped in the 4-2-1 loop and reverting to 1. The amount of steps that it takes for a number to rise to highs and then revert to 1 also varies widely even with numbers starting next to each other.
When you place the trajectories of the different numbers on charts as they rise and revert back to 1 as they go through the math formula the patterns they create are random. The patterns the numbers make look similar to stocks that revert back to the mean after parabolic run ups in price.
Both are examples of geometric Brownian motion. That means if you take the log and remove the linear trend, the fluctuations are random. It’s like flipping a coin each step. If the coin is heads, the line goes up, tails, it goes down. 3x+1 is just like the random volatility of the stock market. Over long-enough periods, the stock market indexes tend to trend upwards, while 3x+1 eventually trends down to 1.
The below chart shows a histogram of the total stopping times (TST) of the integers from 1 to 100 million where the x-axis represents the stopping time and the y-axis represents the frequency. We can see that the largest stopping time does not exceed 500. The most frequent TST is around 175. This provides strong evidence that the Collatz conjecture is true. Since stopping times seem to always be small, computer programs can be written to determine whether the Collatz sequence of a given integer reaches 1 or not. This method has been used to verify the conjecture for all positive integers up to 5 * 260.
If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence would either enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.
The smallest i such that ai < a0 is called the stopping time of n. Similarly, the smallest k such that ak = 1 is called the total stopping time of n. If one of the indexes i or k doesn’t exist, we say that the stopping time or the total stopping time, respectively, is infinite. [2]
Why is 3x+1 impossible?
What is the longest Collatz sequence?
Can the Collatz conjecture be solved?
