The famous mathematical problem which is infamous among Mathematicians
Hey Explorers,
Today's blog is going to be super exciting; it talks about the problem that even world's best mathematicians have not been able to solve.
3N+1 is a simple mathematical problem that can't be solved, at least with the known math.
One of the most prolific mathematician Paul Erdos stated, "Mathematics is not yet ripe enough for such questions".
So what exactly 3N+1 is, lets have a look inside this conjecture.
First introduced in 1937 by Lothar Collatz, this conjecture is known as Collatz Conjecture or Syracuse Problem or Ulam Conjecture or Kakutani's Problem or Thwaites Conjecture or Hasse's algorithm or 3N+1, whoo a lot of names.
3N+1 has 2 basic rules:
- if the number is odd - multiply it with 3 & add 1.
- if the number is even - divide it by 2.
So it goes this simple, assume any number on the natural number series ( 1,2,3,4, ....... )
and apply these two rules.
for instance, lets take 7,
Collatz Conjecture as expressed by number 7
So for number 7 the total stopping time is 17.
However, surprisingly any number you take eventually falls down to 1 and enters the loop 4 - 2 - 1.
Now, every number will have its own path including several peaks & drops finally shrinking to 1 & therefore these are knowns as hailstone numbers referring to the irregular up & down motion of hailstones in thunderstorm.
3N+1 in graphical illustration
There are numbers that takes only few steps to shrink down to 1, while for others it can go to several steps; for example number 26 has a stopping time of 10 but the very next number 27 has 111 steps with highest climbing up-to 9232.
One of several ways to analyze 3N + 1 is by taking the logarithm of values & plotting it, it shows a downwards trends with several wiggles just like the values of crypto market now a days.
This thing is not a coincident, in fact there are several graphs that looks same & this is called Geometric Brownian Motion that states, if you take log & remove the linear trend the fluctuations are random.
Another way is taking the first digit of every value and plotting a histogram, just like this
Over here we observed that for the first billion numbers when we apply Collatz Conjecture, 29.94% values has first digit as 1, and the histogram becomes stable following a common trend as we move towards large values, while the frequency of digits decreases showing fewer than 4.7% starts with 9.
This pattern is known as Benford's law.
And to our surprise this pattern is not unique to 3N + 1, in fact it shows up literarily everywhere from the population of countries to value of physical constants, the market values of companies or the Fibonacci Sequence. You can even detect frauds in income tax returns & elections through the same pattern, how interesting is that now!
But why it shrinks even if at every odd number we multiply 3 & add 1 ?
This is because if you take geometric mean, you'll find that the probability of jumping from one odd to the other is 3/4 or less than 1, as when ever you get an odd number you multiply it with 3 & add 1 making it an even number!
We can also visualize 3N + 1 by plotting a direct graph that looks very similar to a huge family tree:
And if this conjecture is true, every number you consider all the way up to infinity must be connected to a branch that eventually merges in the loop 4 - 2 - 1.
This graph was later modified by rotating it +20 degree anti clock-wise if its odd number & -8 degree clock-wise if its even, finally looking like a Coral or an organic structure, & became popular as a coral scatterplot. This way we can visualize how life evolved from a single cell. Finally we can say, the base of biology is mathematics :)
Now the only question remains is if this conjecture can be proven wrong.
The only two ways this can be proved wrong are:
- if a number grows in a way that takes the sequence to infinity
- if few numbers form an independent loop other than 4 - 2 - 1.
Until now mathematicians have been not able to find a number that satisfies any of these.
To your surprise, till now mathematicians have tested every number till 295,147,905,179,352,825,856; that's a lot of numbers, approx. 300 quintillion numbers have proved that this conjecture is true. And given this information mathematicians have figured this out that any loop other than 4 - 2 - 1 must be 186 billion number long, whoooo quite a looooong loop! This was proved by making a scatterplot:
Scatterplot of 3N +1
But maths says that its still a small amount of numbers, for instance take Polya Conjecture's example:
It states that majority of number have odd prime factors, so if you look at its graph you will notice that the line representing odd factors is always above the line for even.
But then came this smart guy, C. Brin Haselgrove who proved Polys Conjecture wrong at 1.845 x 10^361. This means at this number the line for even will cross the line for odd.
This number (1.845 x 10^361) is 10^340 times bigger than the numbers checked for Collatz Conjecture or 3N + 1.
I know this one is getting long, but this blog is as interesting to write as to read :)
Looking at the graph for all the numbers, we found that lines are always below the line y=x, and by 1994 it was lowered till y=x^0.7925.
In 2019, just 3 years before writing this blog, Terry Tao, one of the best living mathematician proved that this pattern follows a very strict criteria, almost all numbers will end up smaller than any arbitrary function f of x.
Mathematicians also takes help of counter examples, like if we apply 3N + 1 on the negative side of the number line there we have 3 independent loops, but this conjecture was not made to be unproved on the negative side.
Other way to look at 3N + 1 is through Turing machine, which is basically the most simple machine developed to run any algorithm out there & is in fact the base of quantum computers. But the Turing machine faces a halting problem, where it can't stop running when the problem enters the loop 4 - 2 - 1.
This is all about the famous 3N + 1 problem that is infamous among mathematicians, not a lot of them works on this.
This simple math problem is extraordinarily advance.
Or basically the way we were taught simple math & the way we look at it have been always wrong. Just taking all the numbers & testing them is probably not the way to disprove it. We have to find an intelligent process & not just guessing & checking every number.
There you are at the end of a long blog on a small simple math problem that took me weeks to understand, draft & publish.
Now we know why mathematician Jeffrey Lagarias said. "Collatz Conjecture is an extraordinarily difficult problem, completely out of reach of present day mathematics".
BTW, on every part of this blog a separate blog can be written, that how strange math can go :)
A big thank for reading this, Connect with me & lets make today more fascinating.
Reach out to me in comments, contact form on blog or here.
Thanks | Gratitude
0 Comments
Ideas and solutions are always worth to share.
Questions are always worth to be asked.