Guide Collatz Conjecture

Collatz Conjecture​

Collatz Conjecture (a.k.a. 3n + 1 problem) basically says applying these two operations to integers recursively will lead us to the integer 1 and asks if there are any exceptions for that.

Operations and Definitions​

Operations:

• 3n + 1, if n%2 = 1.
• n/2, if n%2 = 0.

Definitions:



Also it is possible for us to define a recursive function which gives us the value of the sequence for an integer with respect to its index.


aᵢ is the value of f applied to n recursively i times.

Let's create a Collatz sequence for integer 17 and examine the function given above for that sequence.

• 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 (indexes).

Let's say i = 0. It means that this function will give us the element at the 0th index of this sequence, which is 17. Indeed, applying Collatz function to integer 17 for 0 times gives us 17.

Let's say i = 3. It means that this function will give us the element at the 3rd index of this sequence, which is 13. When we take i as 3, we see aᵢ is in fact, equal to f(a₂). Since i = 2 > 0, function keeps continuing until i = 0. Let's visualize it for better understanding:

Stopping Time and Total Stopping Time​

Stopping Time:
The smallest i such that aᵢ < a₀ is the stopping time for the sequence.

Total Stopping Time:
The smallest k such that aₖ = 1 is the total stopping time for the sequence.

If none of those indexes exist, we say that both of these stopping times are infinite. Collatz Conjecture asserts that all integers n have a finite total stopping time and this is the assertion which has been (and being) tried to be proven wrong for a long time. As of 2020, this conjecture is checked by a computer for all values up to 2⁶⁸ (295.147.905.179.352.825.856; which is two hundred and ninety five quintillion, a hundred and forty seven quadrillion, nine hundred and five trillion, a hundred and seventy nine billion, three hundred and fifty two million, eight hundred and twenty five thousand, eight hundred fifty six) and could not be proven wrong. Though it is an extremely large number, it still is not enough to say this conjecture is valid for all integers.

Collatz Conjecture Represented in Base 2​

It also can be represented in binary notation. The rule is:

• Append 1 to the right end of the number (which gives us 2n + 1). Then add the number itself to make it 3n + 1 total.
• Remove all 0s at the right end of the number.

Example on 110 (integer 6):

1. 110
2. 110
3. 11 + 111
4. 1010
5. 1010
6. 101 + 1011
7. 10000
8. 10000
9. 1

Since this function gives us sequences which may turn into other sub-sequences or may include a part of some other sequences, visualization of some Collatz sequences gives us tree-looking graphs. Directed graph of the Collatz sequences of first 1000 numbers:

Normalized graph of the Collatz function iteration amount for the first 100 million numbers: