MENU
This is the first article in "The Collatz Conjecture Proof" series, and to date the only article (in the world) that reveals the true nature of the Collatz conjecture.
The author analyzes in detail the algorithm of the Collatz conjecture, its structure, properties and features.
Keywords: Collatz conjecture, algorithm, recursion, recursion step, recursive descent, recursive ascent.
§1. Statement of a question
The Collatz conjecture is one of the most famous unsolved problems in mathematics. Just pick a number, any natural number: If the number is even, cut it in half ([tex]n/2[/tex]); if it's odd, triple it and add 1 ([tex]3n+1[/tex]). Take that new number and repeat the process, again and again.
The conjecture is that these sequences always reach 1.
§2. Introduction
Legends about the unprovability of this problem have long been circulating in mathematical community.
Around 1960, S. Kakutani heard the problem, became interested in it, and circulated it to a number of people. He said
“For about a month everyone at Yale worked on it, with no result. A similar phenomenon happened when I mentioned it at the University of Chicago. A joke was made that this problem was part of a conspiracy to slow down mathematical research in the U.S.”
Mathematicians S. Kurtz and J. Simon in 2007 came to the conclusion that in such a formulation of the question, the problem is undecidable.
The American Mathematical Society published in 2010 compendium "The Ultimate Challenge: The 3x+1 Problem". It talks about unsuccessful attempts to find a solution for 3n+1.
Despite all this, the author Mikhail Martynov found the strength and revealed the true nature of the Collatz conjecture. This article is a breakthrough in 3n+1 and shows that the Collatz conjecture is just part of the another algorithm. To prove the Collatz conjecture, we need to go to another problem.
§3. The full version of the algorithm
The conjecture does the actions [tex]3n+1[/tex] and [tex]n/2[/tex], then the reverse actions are [tex]\frac {n-1}{3}[/tex] and [tex]n[/tex] * 2.
Let's formulate it like this: Take any natural number [tex]n[/tex]; If the number is odd, multiply [tex]n[/tex] by 2; If it's even, subtract one [tex](n-1)[/tex]. If the result of dividing [tex]\frac {n-1}{3}[/tex] is an integer, then it's the next number. If not, then multiply [tex]n[/tex] by 2. In general, we always multiply [tex]n[/tex] by 2 to generate more and more new branches.
Let's look at the sequences according to this scheme:
1, 2, 4, 1
1, 2, 4, 8, 16, 5
1, 2, 4, 8, 16, 5, 10, 3
1, 2, 4, 8, 16, 5, 10, 20, 40, 13
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 7
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 7, 14, 28, 9
1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 44, 88, 29, 58, 19
This is the usual Collatz sequences, only reversed. Let's write this out in more detail.
Let's do the transformation for 1:
Number 1. Multiply by 2. We get 2.
Let's do the transformation for 2:
Number 2. Multiply by 2. We get 4.
Let's do the transformation for 4:
Number 4. [tex]\frac {4-1}{3} = 1[/tex].
Number 4. Multiply by 2. We get 8.
Let's do the transformation for 8:
Number 8. Multiply by 2. We get 16.
Let's do the transformation for 16:
Number 16. [tex]\frac {16-1}{3} = 5[/tex].
Number 16. Multiply by 2. We get 32.
So we are at the first fork! 1, 2, 4, 8, 16 - we have a fork at 5 and 32.
Let's go to fork 5:
1, 2, 4, 8, 16, 5, 10 - we again have a fork at 3 and 20.
1, 2, 4, 8, 16, 5, 10, 3, ...
1, 2, 4, 8, 16, 5, 10, 20, ...
Let's go back to number 32:
1, 2, 4, 8, 16, 32, 64 - we again have a fork at 21 and 128.
1, 2, 4, 8, 16, 32, 64, 21, ...
1, 2, 4, 8, 16, 32, 64, 128, ...
Let's stop there.
The algorithm we just described is a recursion. The [tex]3n+1[/tex] algorithm reproduces the actions of [tex]\frac {n-1}{3}[/tex], only in reverse.
Thus, [tex]3n+1[/tex] is the backward recursion of [tex]\frac {n-1}{3}[/tex]. This is the reason why [tex]3n+1[/tex], repeating the mirror actions of [tex]\frac {n-1}{3}[/tex], descends to 1.
In other words, the [tex]\frac {n-1}{3}[/tex] recursion created a tree of numbers. The recursion [tex]3n+1[/tex] does not yet know what kind of tree it is, but walking along it is doomed to go down to 1:
§4. First conclusions
First, this kind of recursion in mathematics is called course-of-values recursion (see S. Kleene, Introduction to Metamathematics, [chap. IX, §46]).
Secondly, it is obvious that the recursion starts from 1. Number 1 is the progenitor of all branches.
Thirdly, the descent to 1 for each number performs along its own unique branch.
Fourth, number 1 cannot have another progenitor except for 1 itself, because [tex]\frac {n-1}{3}[/tex] and [tex]3n+1[/tex] give one for one (loop 1, 4, 2, 1).
Fifth, the Collatz conjecture is an algorithm derived from the algorithm [tex]\frac {n-1}{3}[/tex] and therefore retains all of its properties.
§5. Even numbers
The iteration of the recursion [tex]\frac {n-1}{3}[/tex] seems incredibly difficult to us because of the even numbers.
Do even numbers affect recursion?
Let's look at the iteration of the recursion:
1
1, 2
1, 2, 4
1, 2, 4, 1
1, 2, 4, 8, 16
1, 2, 4, 8, 16, 5
1, 2, 4, 8, 16, 32
1, 2, 4, 8, 16, 5, 10
1, 2, 4, 8, 16, 5, 10, 3
1, 2, 4, 8, 16, 5, 10, 20, 40
1, 2, 4, 8, 16, 5, 10, 20, 40, 13
...
We apply infinite multiplication by 2, and continue each sequence:
It seems that even numbers act as the connecting links between odd numbers. Let's check this.
§6. Odd numbers
Let [tex]n[/tex] be an odd number. To move forward according to the [tex]\frac {n-1}{3}[/tex] recursion we need to do the following:
- Multiply [tex]n[/tex] by 2 because [tex]n[/tex] is an odd number.
- Suppose after [tex]2n[/tex] there is an odd number [tex]x[/tex]. Then the following equation is true: [tex]\frac {2n-1}{3} = x[/tex].
- We get [tex]x = \frac {2n-1}{3}[/tex].
- The result [tex]\frac {2n}{3} - \frac {1}{3}[/tex] is an integer only if n ≡ 2 mod(3).
For the case n ≡ 1 mod(3) we double [tex]n[/tex]:
- Multiply [tex]n[/tex] by 2, then double it again.
- Suppose after [tex]4n[/tex] there is an odd number [tex]x[/tex]. Then the following equation is true: [tex]\frac {4n-1}{3} = x[/tex].
- We get [tex]x = \frac {4n-1}{3}[/tex].
- The result [tex]\frac {4n}{3} - \frac {1}{3}[/tex] is an integer for n ≡ 1 mod(3).
§7. A tail of the recursion
If we get an odd number n ≡ 0 mod(3) for any step of the recursion, we cannot to continue generating numbers [tex]\frac {2n-1}{3}[/tex], or [tex]\frac {4n- 1}{3}[/tex], or [tex]\frac {8n-1}{3}[/tex], or [tex]\frac {16n-1}{3},[/tex] or any other power of two [tex]2^k[/tex].
Because if n ≡ 0 mod(3), then the solution to the equation [tex](\frac {2^kn}{3} - \frac {1}{3})[/tex] is: [tex]2^kz - \frac {1}{3}[/tex]. It does not have an integer solution.
We'll call numbers n ≡ 0 mod(3) the tail of the recursion.
§8. Special relation ([tex]4x + 1[/tex])
The [tex]\frac {n-1}{3}[/tex] algorithm implies regular multiplication by 2.
No matter what we do, we always multiply by 2. This is the answer to the question why are all odd numbers in Collatz sequences separated from each other by even numbers.
So a situation arises when an odd number can give us two branches of odd numbers (see picture above). In other words, an odd number splits into two odd numbers.
First case.
As we have already found out, if there is such an odd number n ≡ 2 mod(3), then this means that there is also an odd number [tex]x = \frac {2n-1}{3}[/tex].
If we multiply [tex]n[/tex] by 8, we get [tex]y = \frac {8n-1}{3}[/tex]. Any number n ≡ 2 mod(3) can be represented as [tex]3k-1[/tex]. Then the equation [tex]y = \frac {8n-1}{3}[/tex] reduces to the solution:
[tex]y = \frac{8(3k-1)-1}{3} = \frac{24k-9}{3}=8k-3[/tex], which of course has an integer solution.
Is there a relation between these numbers: [tex]x[/tex] and [tex]y[/tex]?
[tex]x = \frac {2n-1}{3}, \; \; n = \frac {3x+1}{2}[/tex]
[tex]y = \frac {8n-1}{3}, \; \; n = \frac {3y+1}{8}[/tex]
[tex]\frac {3x+1}{2} = \frac {3y+1}{8}[/tex]
[tex]y=4x+1[/tex]
Yes, there is a relation. Odd number n ≡ 2 mod(3) gives us always odd numbers: [tex]x = \frac {2n-1}{3}[/tex] and [tex]y=4x+1.[/tex]
Second case.
As we have already found out, if there is such an odd number n ≡ 1 mod(3), then this means that there is also an odd number [tex]x = \frac {4n-1}{3}[/tex].
If we multiply [tex]n[/tex] by 16, we get [tex]y = \frac {16n-1}{3}[/tex]. Any number n ≡ 1 mod(3) can be represented as [tex]3k-2[/tex]. Then the equation [tex]y = \frac {16n-1}{3}[/tex] reduces to the solution:
[tex]y = \frac{16(3k-2)-1}{3} = \frac{48k-33}{3}=16k-11[/tex], which of course has an integer solution.
Is there a relation between these numbers: [tex]x[/tex] and [tex]y[/tex]?
[tex]x = \frac {4n-1}{3}, \; \; n = \frac {3x+1}{4}[/tex]
[tex]y = \frac {16n-1}{3}, \; \; n = \frac {3y+1}{16}[/tex]
[tex]\frac {3x+1}{4} = \frac {3y+1}{16}[/tex]
[tex]y=4x+1[/tex]
Yes, there is a relation. Odd number n ≡ 1 mod(3) gives us always odd numbers: [tex]x = \frac {4n-1}{3}[/tex] and [tex]y=4x+1.[/tex]
Thus, we get the iteration of the recursion between all odd numbers:
[tex]\frac{2n-1}{3}[/tex] for the case n ≡ 2 mod(3),
[tex]\frac{4n-1}{3}[/tex] for the case n ≡ 1 mod(3),
[tex]n=n[/tex] for the case n ≡ 0 mod(3),
and regular using [tex]4x+1[/tex] for new numbers.
§9. New algorithm
We removed all even numbers from the recursion and simplified the algorithm to three rules, [tex]\frac{2n-1}{3}[/tex], [tex]\frac{4n-1}{3}[/tex] and [tex]4x+1[/tex].
Let's write this out in more detail.
The iteration №1.
Number 1. n ≡ 1 mod(3), use [tex]\frac{4n-1}{3}, \quad \frac {4-1}{3} = 1.[/tex]
Number 1. 4n+1 = 5.
The iteration №2.
Number 5. n ≡ 2 mod(3), use [tex]\frac{2n-1}{3}, \quad \frac {10-1}{3} = 3.[/tex]
Number 5. 4n+1 = 21.
The iteration №3.
Number 3. n ≡ 0 mod(3), the tail of the recursion.
Number 3. 4n+1 = 13.
The iteration №4.
Number 13. n ≡ 1 mod(3), use [tex]\frac{4n-1}{3}, \quad \frac {52-1}{3} = 17.[/tex]
Number 13. 4n+1 = 53.
The iteration №5.
Number 17. n ≡ 2 mod(3), use [tex]\frac{2n-1}{3}, \quad \frac {34-1}{3} = 11.[/tex]
Number 17. 4n+1 = 69.
The iteration №6.
Number 11. n ≡ 2 mod(3), use [tex]\frac{2n-1}{3}, \quad \frac {22-1}{3} = 7.[/tex]
Number 11. 4n+1 = 45.
The iteration №7.
Number 7. n ≡ 1 mod(3), use [tex]\frac{4n-1}{3}, \quad \frac {28-1}{3} = 9.[/tex]
Number 7. 4n+1 = 29.
etc.
§10. How can we get the number 27 ?
To get the number 27, we just need to start the recursion from 1 and walk along the following branch:
1 [tex]\rightarrow[/tex] 5 [tex]\rightarrow[/tex] 3 [tex]\rightarrow[/tex] 13 [tex]\rightarrow[/tex] 53 [tex]\rightarrow[/tex] 35 [tex]\rightarrow[/tex] 23 [tex]\rightarrow[/tex] 15 [tex]\rightarrow[/tex] 61 [tex]\rightarrow[/tex] 81 [tex]\rightarrow[/tex] 325 [tex]\rightarrow[/tex] 433 [tex]\rightarrow[/tex] 577 [tex]\rightarrow[/tex] 769 [tex]\rightarrow[/tex] 3077 [tex]\rightarrow[/tex] 2051 [tex]\rightarrow[/tex] 1367 [tex]\rightarrow[/tex] 911 [tex]\rightarrow[/tex] 607 [tex]\rightarrow[/tex] 2429 [tex]\rightarrow[/tex] 1619 [tex]\rightarrow[/tex] 1079 [tex]\rightarrow[/tex] 719 [tex]\rightarrow[/tex] 479 [tex]\rightarrow[/tex] 319 [tex]\rightarrow[/tex] 425 [tex]\rightarrow[/tex] 283 [tex]\rightarrow[/tex] 377 [tex]\rightarrow[/tex] 251 [tex]\rightarrow[/tex] 167 [tex]\rightarrow[/tex] 111 [tex]\rightarrow[/tex] 445 [tex]\rightarrow[/tex] 593 [tex]\rightarrow[/tex] 395 [tex]\rightarrow[/tex] 263 [tex]\rightarrow[/tex] 175 [tex]\rightarrow[/tex] 233 [tex]\rightarrow[/tex] 155 [tex]\rightarrow[/tex] 103 [tex]\rightarrow[/tex] 137 [tex]\rightarrow[/tex] 91 [tex]\rightarrow[/tex] 121 [tex]\rightarrow[/tex] 161 [tex]\rightarrow[/tex] 107 [tex]\rightarrow[/tex] 71 [tex]\rightarrow[/tex] 47 [tex]\rightarrow[/tex] 31 [tex]\rightarrow[/tex] 41 [tex]\rightarrow[/tex] 27.
§11. How to do it on a computer?
You need to recursively execute the following code to generate new numbers:
- Code: Select all
procedure UseRules(n)
If (n % 3 = 1) then
begin
FirstNumber = (4*n - 1)/3;
SecondNumber = 4*n + 1;
end;
If (n % 3 = 2) then
begin
FirstNumber = (2*n - 1)/3;
SecondNumber = 4*n + 1;
end;
If (n % 3 = 0) then
begin
FirstNumber = 0; // the tail of the recursion.
SecondNumber = 4*n + 1;
end;
AddNewValueToTable(FirstNumber);
AddNewValueToTable(SecondNumber);
end;
It takes 500 iterations to cover the interval from [1 ... 100].
It takes 25000 iterations to cover the interval from [1 ... 1000].
It takes 1 million iterations to cover the interval from [1 ... 10000].
---
Best regards,
Author Mikhail Martynov, Russia, Orenburg, programmer.