Collatz Conjecture is also known as 3x+1 problem.
This is one of the simplest impossible mathematical problems.
It is stated as:
|
Cn = { |
| Cn-1 / 2 if Cn-1 is even |
| 3 Cn-1 + 1 if Cn-1 is odd |
Most number series sooner or later diverge to 1 - that is: to the cycle 4, 2, 1, which repeats forever.
Example: Number 10: 10 (/2) -> 5 (*3+1) -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> ...
However, we cannot be certain that this is true for all numbers. It is completely possible that there exists another cycle to which some number series converge. One of the simplest ways to prove that not all numbers converge to 1 is to find such a cycle (in text: a different cycle) . People have been tackling this problem since 1937 when Lothar Collatz proposed it, but have not yet been able to find a different cycle. Many strong computers were put to the test, yet without avail. But for now, let us see how this problem can be tackled.
Choose a random number and check if it leads to a different cycle. Do this for all numbers.
Example:
(3) -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
(5) -> 16 -> 8 -> 4 -> 2 -> 1
(6) -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Remember all previous numbers, so we do not check them multiple times.
Example:
(3) -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
(5) -> /
(6) -> 3 -> /
This representation has been thoroughly tested with numbers up to at least 100 billion, without an additional cycle ( 4 -> 2 -> 1 ) being found.
Source: https://en.wikipedia.org/wiki/Collatz_conjecture
Paradigm shift: Forget individual numbers. Check for possible cycles!
Instead of checking each number, we should check what kind of cycles could exist and from there on determine which numbers would be there.
Mark operations: "o = x/2" and "t = 3x+1"
So a cycle too would represent equation: x = (((3x+1)/2)/2)
Remember: after a cycle, we get the same number.
When we solve x = (((3x+1)/2)/2), we get x = 1
Cycle too clearly marks cycle 1 -> 4 -> 2 -> 1 and stand as such the only.
Another possible cycle would be eg. ototo,
which resolves to equation x = ((((x/2)*3+1)/2)*3+1)/2
and solution to this is x = -10 .
This marks the cycle: (-10) -> (-5) -> (-14) -> (-7) -> (-20) -> (-10)
We however seek only cycles with natural numbers, so this is not a good solution, however the method proves worthy.
I had taken the liberty of continuing on this trail of thought and try to solve this problem using the second mental representation.
In the course of two months I have written an algebraic calculator, that is able to calculate (at least) linear one variable equations, and a cycle generator. Cycle generator creates complex cycles, in the form mentioned above, starting with one and increasing the number of operations in the cycle. This way all possible cycles can be tested. After the variable for each cycle is calculated, validation tests are run on it: the number must be a positive (non negative and not zero) integer (whole number) and each of the operations in the cycle must be executed on an appropriate even or odd number (o on even and t on odd numbers). Additionally, double cycles are also prevented (eg. cycle tootoo is just two consecutive cycles too). If the cycle solution passes all of these tests, it is a valid solution of this problem.
I have successfully tested this approach with cycles up to 30 operations, proving that a possible additional cycle would have to have more than 30 operations.
Disclaimer:
The second mental representation was not (yet) able to solve the problem, however, it still brings an interesting insight on it.
Additionally, I find it very interesting that the problem remains unsolvable even in this approach.
Source: https://xkcd.com/710/