Proof of Collatz conjecture - rabbit2202のブログ

Convergence of $\boldsymbol{log_2 3\hspace{2pt}/\hspace{2pt}2}$

From Wikipedia "Collatz Conjecture"

The Collatz conjecture in mathematics asks whether repeating two simple arithmetic operations will eventually transform every positive integer into one. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term 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.

We show two methods, which are said to be the conditions for confirming the end state of the Collatz problem and proof of it.

Check the end status

1. The value does not circulate

The value does not circulate for each individual operation
No value circulation due to multiple operations

2. The value does not spread

In binary numbers, the growth rate of the lowest digit is sufficiently higher than that of the highest digit
Judgment of the state where the value expands
The expanding state is finite
When repeated occurrences and disappearances, the growth rate of contraction is sufficiently higher than the growth rate of expansion

Check the end status

For the Collatz problem, perform operation 5

At this point, 16 is 2 to the 4th power, so it can be seen that it ends. In binary

Will be. Next, if you dare to perform an operation on 1, which is the convergence value,

Will be. As a result, it can be seen that the value in which several two digits of the binary number 01 are lined up converges to 1. As shown shortly after, there is no other case. Hereafter, unless otherwise specified, the numbers in the formula are binary numbers, the numbers in parentheses are decimal numbers (example "1001(9)"), and the numbers after the comma are the remainder numbers of 3 (example "1011(11,2)").

Example of not converging to 1 with one odd number of operations:

When two 1s are adjacent

When two 1s are two digits apart

Example of converging to 1 with one odd number of operations:

When 10 01s are lined up

If you calculate this in decimal,

There is virtually no point in dividing an even number by 2, and these are "multiples of 2", which is a state in which the most significant digit and the least significant digit of the value of 1 when viewed in binary are one.

In other words, the essence of the Collatz problem is that "when an odd number of operations $\boldsymbol{N \times 3 + 1}$ is repeated, it always becomes a multiplier of 2." However, what is added after multiplying by 3 is not 1 but the same value as the minimum digit of the value of 1 in the binary value.

The calculation result is not congruent with 0 with 3 as the modulo. This is because the odd-numbered operation result $N \times 3 + 1$ is always congruent with 1 with 3 as the modulo, so there is no 3 in the factor of that number.

[Reason why values do not circulate]

The value does not circulate for each individual operation

If the values circulate, which of the three operations listed below is performed?

First, assuming that it circulates in $N \times 3$ , if the value to be calculated at the beginning is $N_1$ , the value after the calculation is $M_1$ , the value to be circulated is $N_2$ , and the circulated value after the calculation is $M_2$ ,


 (a)
 (b)

Substituting (a) into (b)

It is inconsistent with $\boldsymbol{N_1 \neq N_2}$ . This assumes that there is a value before the operation, but what about the initial value without the value before the operation?

However, the initial value without a value before the calculation is a multiple of 3, and since the multiple of 3 does not appear after the calculation, it will not be the same value. It is clear that $\boldsymbol{N + 1}$ also gives him the same contradictory results as $\boldsymbol{N \times 3}$ .

$\boldsymbol{N / 2^{n}}$ is also inconsistent if the indices are equal.

However, $N / 2^{n}$ may be equal after the operation due to the difference in the exponents. In fact, if it becomes 29 or 117 after performing several operations from 7 as shown below, the same value will be obtained in even-numbered operations, but is it possible that it is an actual continuous operation?

The fact that the order of the upper digits 0 and 1 is the same and only the number of the lower 0s is different after the odd number operation does not appear in the operation starting from a multiple of the initial value 3 to becoming 1. It corresponds to the confluence when the initial value, a multiple of 3, is started with another value. Therefore, even the operation of $\boldsymbol{N \times 2^{n}}$ does not circulate.

No value circulation due to multiple operations

The fact that the values circulate means that those values do not appear until the operation is repeated and converged to 1.

Assuming that there is a 1 in the upper digit, if you perform operations on the lowest digit continuously as shown below, you can see that all the digits are valid without being missed(The even operation $N / 2^{n}$ is omitted to fix the digit, and +1 in the odd operation conversely performs $+ 1 \times 2^{n}$ ).

If some digits are not valid, they may not converge to 1. It happens by removing the least significant digit in the case of his $N\times3-1$ , which is a variant of odd operations.

Looking at the number that converges to 1 by this operation, the minimum value is 3 and the second place is 11, and 5, 7 and 9 in between do not converge to 1 and circulate, but this is due to -1. This is because the lowest value is not valid. 5 and 7 go directly, 9 goes to 13, 19, and 7 and circulates.

[Reason why the value does not spread]

The diffusion of values occurs when the calculation result expands on average. Individual expansion is due to odd number of operations.

In binary numbers, the growth rate of the lowest digit is sufficiently higher than that of the highest digit.

The final convergence to 1 means that the least significant digit 1 in the binary number catches up with the most significant digit 1 when only odd-numbered operations are performed(Here, the blue 1 becomes the red 1).

Normal      Odd-only             Opening
 operations  operations           of top and bottom digits

Since the most significant digit in binary is tripled, $log_2 3 = 1.58$ digits in a stable state. The last 0, which is the extension of the lowest digit, is definitely one digit by +1. If the adjacent high digit is 0, it becomes 2 by the carry.

 Double digit growth
 Single digit growth

The probability of being vacant from the adjacent high-order digit to the end is

Therefore, the extension is two digits as in the case where the adjacent high-order digits are 0. Therefore, the ratio of growth between the most significant digit and the least significant digit is $1.58 / 2 = 0.79$ . This is a sufficient ratio to converge, and if it is not an infinite value, it will eventually converge to 1.

７Trends in growth of the most significant digit and the least significant digit using 7 as an example

Number of operations	Normal operation		Odd-only operations		Number of digit growth
Number of operations	Normal operation		Odd-only operations		Most significant digit	Last digit
0	111	7	111	7	0	0
1	1011	11	10110	22	2	1
2	10001	17	1000100	68	4	2
3	1101	13	11010000	208	5	4
4	101	5	1010000000	640	7	7
5	1	1	100000000000	2048	9	11

Growth rate of the highest digit (1.8) = Number of growth of digits (9) / Number of operations (5)
Growth rate of the lowest digit (2.2) = Number of growth of digits (11) / Number of operations (5)
Growth rate ratio (0.818) = Growth rate of the highest digit (1.8) / Growth rate of the lowest digit (2.2)

Growth rate ratio between upper digit and least significant digit (value only is binary)

Kinds	Value / Number of digits	Number of operations	Most significant digit		Last digit		Growth rate ratio (Most digit / Least significant digit)
Kinds	Value / Number of digits	Number of operations	Number of digits	Growth rate	Number of digits	Growth rate	Growth rate ratio (Most digit / Least significant digit)
0	11(3)	2	4	2	5	2.5	0.8
0	101(5)	1	2	2	5	5	0.4
0	111(7)	5	9	1.8	11	2.2	0.818
0	1001(9)	6	10	1.667	13	2.167	0.769
0	1011(11)	4	7	1.75	10	2.5	0.7
1	101	528	838	1.587	938	1.777	0.893
2	101	210	334	1.590	434	2.067	0.769
3	101	268	427	1.593	527	1.966	0.810
1	1001	4923	7805	1.585	8805	1.789	0.886
2	1001	2417	3832	1.585	4832	1.999	0.793
3	1001	2621	4156	1.586	5156	1.967	0.806
1	10001	48126	76280	1.585	86280	1.793	0.884
2	10001	24131	38248	1.585	48248	1.999	0.793
3	10001	24300	38546	1.586	48546	1.998	0.794

Kinds

0: Value
1: 111...111
2: 100...001
3: 11

Judgment of the state where the value expands

The operation result of $\boldsymbol{(N \times 3 + 1) / 2}$ becomes an odd number is the maximum value of the number congruent with 2 modulo 3, and only in this case, it is expanded even if an even number operation is performed. This is limited to the case where the least significant two digits of the value before the operation are 11, for the following reasons.

Three times the number 100, which is one larger than 11, is congruent with 0 with 3 as the modulo ... (a)
Multiplying 11 and adding 1 makes it congruent with 1 with 3 as the modulo ................... (b)
If you add both, you can divide by 2, and if you divide by 2, you get an odd number ....... (c)
The above calculation result is congruent with 2 with 3 as the modulo ............................. (d)

(a)
(b)
(c)
(d)

Since 3 times the binary number 100 is congruent with 0 modulo 3, 3 times the binary number whose last 2 digits are 00 is always congruent with 0 modulo 3.
Therefore, if the last two digits are 11, all odd numbers are calculated to be the maximum value of a number congruent with 2 modulo 3.

The expanding state is finite

When multiplying by 3 with consecutive 1s in the upper digit, the last 2 digits are always 01, the first 2 digits are 10, and the middle is filled with 1. This is because there is no carry from the bottom and the top 1 is cut off.

If there is a continuous 1 in the lowest digit, adding 1 makes the continuous 1 a value one digit less than before the operation. That is, when the calculation is repeated in these states, the value expands by the number of consecutive one digit and then converges.

Therefore, the expansion depends on the continuous 1s of the lowest digit in the value before the operation, but if the number of consecutive 1s is finite, it will eventually converge.

Example of expanding and then reducing for two consecutive times:

When repeated occurrences and disappearances, the growth rate of contraction is sufficiently higher than the growth rate of expansion.

Looking at the one with a small value of the lowest digit 11 that can be expanded

This cannot occur because 11 (3,0) is a multiple of 3.
111 (7,1) is caused by 1001 (9,0).

Since 9 is also a multiple of 3, this cannot be generated, but this can be avoided by adding the binary number 10 to the adjacent high-order digits, and the number of 11 to be generated can be increased by the same number of digits.

Condition to expand the generated value (There are 3 or more consecutive 1s in the lowest digit, and the number increases by 2 digits)

Condition to generate an expanded value (the least significant digit is 01 and one or more 10s in the adjacent high digit)

The condition for generating an expanding value and the condition for arranging 01 for reducing digits are values in which the order of 0 and 1 after the third digit is reversed, and it can be said that the probabilities of generating these are equal. However, the number of enlargement / reduction operations is different, and enlargement (number of enlargement digits) > reduction (1).

    Reduction


    Expansion

As for the growth rate between the most significant digit and the least significant digit, if the number of digits of the initial value is set to T, the number of expansion operations is $T-2$ ,

    Reduction calculation





    Expansion calculation

The growth rate of the most significant digit at the expanded value is not accurate, but the calculated value as $log_2 x(x=3.5)$ is $8.81$ , but it is less than 8 in the actual calculation. Therefore, if the elongation of the highest digit is 8, the ratio to the reduced value is 1: 4, and even if the expanded value is generated and expanded repeatedly, it will finally converge. Furthermore, for reduction with a small number of operations, reduction with $log_2 3 / 2$ as a ratio is added by the difference in the number of operations (enlargement (T-1) -reduction (1) = (T-2)).

When the operation is performed with the number of digits T = 114, the following results are obtained. In the case of reduction, only one operation is always performed, so the difference increases as the number of digits increases.



State to shrink
Initial value (114 digits)
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
Operation result-End of reduction
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Number of operations 1 time

State that keeps expanding
Initial value (114 digits)
101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001
Calculation result-End of expansion (number of digits 293, least significant digit 179)
10110111000000110100000101010111100111010000101001010001011101110100101110111110111001100111100010000110000011010010010101101100001000010001100011100111000110100110110010110000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Number of operations 113 times

In addition, although the value to be expanded can be obtained in other states such as $11101(29,2)$ , the density of 1 becomes high ( $density \gt 1/2$ ), which causes unnecessary values and digits to be expanded. Efficiency (number of enlargements / number of digits of initial value) becomes worse.

From the above

Even if the operation $(N \times 3 + 1) / 2^{n}$ is repeated, it does not circulate and does not spread.
∴ Collatz's prediction is correct

Written notice.
I translated from Japanese original in machine translation software on the Internet. I translated it into Japanese with the same software and confirmed it, but I think there are imprecise and unclear places.

The original text is below.
コラッツ予想の証明 - $log_2 3\hspace{2pt}/\hspace{2pt}2$ の収束