Collatz Conjecture - Explaining the convergence

Summary:

Collatz conjecture has remained an unsolved mathematical puzzle.  In this note, we propose a “solution” to the conjecture.  The approach involves transformation of Collatz sequence by combining sequential steps, which helps reveal the underlying mechanism responsible for the observed convergence to unity.

1. Problem Statement

Collatz conjecture states that if

a) one starts with a positive natural number;

b) divides it by 2 if even;

c) triples it and adds 1 if it is odd;

d) repeats (b) and (c) on the number thus obtained and repeats this step multiple times;

the number would eventually converge to 1, whereafter these operations would keep yielding 1,4,2,1,4,2…

Therefore, “Collatz Function” f(N) may be defined as follows:

f(N) = N/2, if N is an even number

f(N) = (3N+1), if N is an odd number

Thus, for a starting number, the resulting series would be as follows:

27-->82-->41-->124-->62-->31-->94-->47-->142-->71-->214-->107-->322-->161-->484-->242 and so on.

 

2. Transforming Collatz Function:

The solution approach considers the following transformation:

Transformation 1:  For an odd number, consider (3N+1) and division by 2 as a single operation (3N+1)/2

For an odd number, 3N+1 will always be an even number (as 3N will be odd and sum of 3N and 1 will be even).  Therefore, we consider the next operation (i.e. division by 2) as a single operation.  Therefore, if starting number is 27, the next number would be (3*27+1)/2 = 41.

 

Transformation 2: Consider successive (3N+1)/2 as a single operation until an even number is reached

 

For an odd number, if the resulting number after (3N+1)/2 is still an odd number, the next (3N+1)/2 is also considered as part of the same operation.  This is continued until an even number is obtained.

 

Transformation 3: Consider successive N/2 as a single operation until an odd number is reached.

 

Similarly, for an even number if the resulting number after N/2 is still an even number, the next N/2 is also considered as part of the same operation.  This is continued until an odd number is obtained.

 

Thus, if 27 is the starting number, the resulting series in the initial and reformulated problem would appear as follows:

Initial:

27à82à41à124à62à31à94à47à142à71à214à107à322à161à484à242

Reformulated:

27à41à62à31à242                                                                                              

 

3. Multiplication Steps (3N+1)/2

The standard notation of even and odd numbers is (2i-1)2ⁿ and (2i-1)2ⁿ-1

If we start with an odd number N₀= (2i-1)2ⁿ-1, the successive (3N+1)/2 operations would appear as follows:

 

N₁ = (3N₀+1)/2 = [3{(2i-1)2ⁿ -1}+1]/2 = 3(2i-1)2^n-1 -1

N₂ = (3N₁+1)/2 = [3{3(2i-1)2^n-1 -1}+1]/2 = 3²(2i-1)2^n-2 -1

N₃ = (3N₂+1)/2 = [3{3²(2i-1)2^n-2 -1}+1]/2 = 3³(2i-1)2^n-3 -1

…

N_k = (3N_k-1+1)/2 = [3{3^k-1(2i-1)2^n-k+1 -1}+1]/2 = 3^k(2i-1)2^n-k-1

…

so on till

 

N_n = (3N_n-1+1)/2 = [3{3^n-1(2i-1)2¹ -1}+1]/2 = 3ⁿ(2i-1)-1

 

As (2i-1) and 3ⁿ are always odd number, their product is always odd.  Therefore, N_n= (2i-1)3ⁿ-1 is always even.  It can also be seen that no in between value between N₀ and N_n odd numbers (as they are odd*power of 2 – 1).

 Thus,

 

For starting odd number N₀ = (2i-1)2ⁿ-1, the final (even) number is N_n = (2i-1)3ⁿ-1

 The sample table below describes the initial (odd) and final (even) values:

 

2i-1	Starting Odd Nos:  N0=(2i-1)2n-1						Terminal Even Nos:  Nn=(2i-1)3n-1
	1	2	3	4	5	6	1	2	3	4	5	6
1	1	3	7	15	31	63	2	8	26	80	242	728
3	5	11	23	47	95	191	8	26	80	242	728	2186
5	9	19	39	79	159	319	14	44	134	404	1214	3644
7	13	27	55	111	223	447	20	62	188	566	1700	5102
9	17	35	71	143	287	575	26	80	242	728	2186	6560
11	21	43	87	175	351	703	32	98	296	890	2672	8018
13	25	51	103	207	415	831	38	116	350	1052	3158	9476
15	29	59	119	239	479	959	44	134	404	1214	3644	10934

 As can be seen, the resulting table has repeating values.  There are two ways to reduce the above table to display only the unique values: 

• It may be noted that the values in the first column (n=1) of the even series on the right side is a superset of the values in the remaining columns.  This can be logically explained.  The odd numbers on the left side shift leftwards by one column upon each successive (3N+1)/2 operations.  For example N₀=7 moves from column 3 to column 2 (N₁=11), then to column 1 (N₂=17), which finally becomes an even number (N₃=26).  Therefore, the value 26 would appear against 7, 11 and 17 in these columns as highlighted in the above sample table.

Substituting n=1 in (2i-1)3ⁿ-1, we get the series  {6i-4, i ∈ ℕ } which represents the entire set of even values obtained as terminal values as a result of successive (3N+1)/2 operations.

• For the values of i which are divisible by 3, the resulting even values are repeated from an earlier column.  This too can be mathematically explained.  Let’s say 2i-1 = 3(2i-1) à (2i-1)3ⁿ-1 = (2j-1)3ⁿ⁺¹-1.    Therefore, we may ignore these values of 2i-1 to obtain a unique set of even values in the above table, as shown below.

 

	1	2	3	4	5	6
1	2	8	26	80	242	728
5	14	44	134	404	1214	3644
7	20	62	188	566	1700	5102
11	32	98	296	890	2672	8018
13	38	116	350	1052	3158	9476
17	50	152	458	1376	4130	12392
19	56	170	512	1538	4616	13850
23	68	206	620	1862	5588	16766
25	74	224	674	2024	6074	18224
29	86	260	782	2348	7046	21140
31	92	278	836	2510	7532	22598
35	104	314	944	2834	8504	25514
37	110	332	998	2996	8990	26972
41	122	368	1106	3320	9962	29888
43	128	386	1160	3482	10448	31346
47	140	422	1268	3806	11420	34262

Thus, we may obtain the unique set by either considering only the first column (n=1); or by eliminating the values of (2i-1) which are divisible by 3.

 After removing (2i-1) values divisible by 3 (i.e. {6i-3}, i.e. 3, 9, 15…), we are left with

·        {6i-5} i.e. {1,7,13… } à (6i-5)3ⁿ-1 and

·        {6i-1} i.e. {5,11,17… } à (6i-1)3ⁿ-1

 

4. Division Steps (N/2)

We are now required to successively divide the even values (obtained in #3) until we are left with an odd number.

 A sample transformation table is shown below.

 

	Starting Even Numbers =(2i-1)3n-1							Terminal Odd Numbers
	1	2	3	4	5	6		1	2	3	4	5	6
1	2	8	26	80	242	728		1	1	13	5	121	91
5	14	44	134	404	1214	3644		7	11	67	101	607	911
7	20	62	188	566	1700	5102		5	31	47	283	425	2551
11	32	98	296	890	2672	8018		1	49	37	445	167	4009
13	38	116	350	1052	3158	9476		19	29	175	263	1579	2369
17	50	152	458	1376	4130	12392		25	19	229	43	2065	1549
19	56	170	512	1538	4616	13850		7	85	1	769	577	6925
23	68	206	620	1862	5588	16766		17	103	155	931	1397	8383
25	74	224	674	2024	6074	18224		37	7	337	253	3037	1139

In the above table, the even numbers are expressed as a mathematical formula (derived in previous section) but the numbers on the right side defy mathematical expression.  This is because the starting series needs to be transformed into (2j-1)2^m format, so that the powers of 2 (i.e. 2^m) can be stripped away through sequential divisions by 2, leaving the terminal odd number (2j-1).

Nonetheless, lets try to rearrange the series {6i-4} obtained through the multiplication step as powers of 2.

We notice that

4*(6i-4) = 24i-16 = 6(4i-2)-4

Thus, (6i-4)4^n-1 belongs to the series {6i-4}. 

 

Even Series (6i-4)22n-2
2	8	32	128	512	2048
8	32	128	512	2048	8192
14	56	224	896	3584	14336
20	80	320	1280	5120	20480
26	104	416	1664	6656	26624
32	128	512	2048	8192	32768
38	152	608	2432	9728	38912
44	176	704	2816	11264	45056
50	200	800	3200	12800	51200
56	224	896	3584	14336	57344
62	248	992	3968	15872	63488
68	272	1088	4352	17408	69632
74	296	1184	4736	18944	75776

It may be noted that every fourth row in the above table has duplicated values from an earlier row.  This is because the columns are populated as multiples of 4.    Eliminating these rows, we get the following unique set which is the same (6i-4) series rearranged as increasing multiples of 2.

 

Even Series
2	8	32	128	512	2048
14	56	224	896	3584	14336
20	80	320	1280	5120	20480
26	104	416	1664	6656	26624
38	152	608	2432	9728	38912
44	176	704	2816	11264	45056
50	200	800	3200	12800	51200
62	248	992	3968	15872	63488
68	272	1088	4352	17408	69632
74	296	1184	4736	18944	75776

The above series can be divided into the following three sub-series: 

• (24i-22)2^2n-2  : 2, 26, 50, 74…
• (24i-10)2^2n-2  : 14, 38, 62, 86…
• 4(6i-1)2^2n-2   : 20, 44, 68, 92…

It may be seen that the root multiplier first two sub-series is divisible by 2, i.e. 24i-22 à 2*(12i-11), and 24i-10 à 2(12i-5); but that of the third sub-series is divisible by 4, i.e. 24i-4 à 4(6i-1).

Thus, the odd multiplier for the three series are :  12i-11, 12i-5 and 6i-1.  Further, it may be seen that 12i-11 and 12i-7 can be combined to form the series 6i-5.

Consequently, the root multipliers for the odd series, 6i-1 and 6i-5, as same as those for the even series!

The odd series thus obtained would be:

Even Series: N = 2(6i-5)2^2n-2 = (6i-5)2^2n-1à (2N-1)/3 = (2*(6i-5)2^2n-1-1)/3 = [(6i-5)2²ⁿ-1]/3

Even Series : N = 4(6i-1)2^2n-2 = (6i-1)2²ⁿà (2N-1)/3 = (2*(6i-1)2²ⁿ-1)/3 = [(6i-1)2²ⁿ⁺¹-1]/3

 

Therefore, we may conclude that for a starting odd number series,  (2i-1)2n-1, a)      Multiplication steps result in the even series (2i-1)3n-1 b)     The superset of even values is represented by (6i-4) or by (6i-5)3n-1 and (6i-5)3n-1.       c)     The superset (6i-4) can also be expressed as (6i-5)22n-1 and (6i-5)22n.      d)     Division step would strip away the powers of 2, leaving us with (6i-5) and (6i-1).

5. Loss of Traceability

While we are able to mathematically correlate the initial odd number (2i-1)2ⁿ-1 with the resulting even number (2i-1)3ⁿ-1, it appears difficult to find a mathematical correlation of (2i-1)3ⁿ-1 to its corresponding odd number obtained after the division steps.  We are only able to deduce that the odd number would belong to either (6i-1) or (6i-5) series.

Unless such a correlation is discovered, it is difficult to mathematically “prove” the convergence of Collatz sequences.   However, it is still possible to logically explain the underlying mechanism responsible for the convergence.

Note:  Kindly refer to the Annexure where certain patterns are described, which may potentially help bring back the traceability.  This is still under further investigation.  However, the discoveries thus far in this note are still sufficient to logically explain the convergence.

6. Explaining the Convergence

To explain the convergence of Collatz sequence, we will approach the problem backwards.  We have seen in the previous section that the even series (as powers of 2) can be described as (6i-5)2^2n-1 or (6i-1)2²ⁿ.

6.1 Defining inverse function

Let’s define function “g” with arguments “N” and “n”; N being a natural number and n being the number of times N is subjected to (2N-1)/3 operations to yield natural numbers.

g(N,1) = (2N-1)/3 = (2N+2-3)/3 = 2(N+1)/3-1

g(N,2) = [2(2N-1)/3-1]/3 = (4N-5)/9 = 4(N+1)/9-1

g(N,3) = [2(4N-5)/9-1]/3 = (8N-19)/27 = 8(N+1)/27-1

and so on…

Therefore, g(N,n) = (2/3)ⁿ(N+1) – 1;  where f(N,n); N; n ∈ ℕ

6.2 First Series E₁

 Lets begin with the first E₁=1*2^2n-1

E1 =1*22n-1	2	8	32	128	512
g(E1,1)	1	5	21	85	341
g(E1,2)		3			227
g(E1,3)					151

 

 

 

6.2 The Second Series E₂

Lets construct the next series E₂ from the odd numbers derived from “parent” series E₁.  To do this, we would multiply the odd numbers with powers of 2.

 As seen in earlier section,

for series {6i-5}, we multiply by 2ⁿ

for series {6i-1}, we multiply by 2^n-1

for series {6i-3}, no even series would yield further natural numbers.

 

 

E2=5*22n 20 80 320 1280 5120 g(E2,1) 13 53 213 853 3413 g(E2,2)   35     2275 g(E2,3)   23       g(E2,4)   15          E2=341*22n 1364 5456 21824 87296 g(E2,1) 909 3637 14549 58197 g(E2,2)     9699   g(E2,3)         g(E2,4)	E2=85*22n-1 170 680 2720 10880 43520 g(E2,1) 113 453 1813 7253 29013 g(E2,2) 75     4835   g(E2,3)       3223       E2=227*22n 908 3632 14528 58112 g(E2,1) 605 2421 9685 38741 g(E2,2) 403     25827

3.3 The Third Series E₂

 Similarly, we can construct the next series E₃ from the odd numbers derived from “parent” series E₁.

E2=13*22n-1 26 104 416 1664 6656 g(E2,1) 17 69 277 1109 4437 g(E2,2) 11     739   g(E2,3) 7           E2=35*22n 140 560 2240 8960 g(E2,1) 93 373 1493 5973 g(E2,2) 995 g(E2,3) 663 g(E2,4)

E2=53*22n 212 848 3392 13568 54272 g(E2,1) 141 565 2261 9045 36181 g(E2,2)     1507         E2=23*22n 92 368 1472 5888 g(E2,1) 61 245 981 3925

This process may be continued to define the hierarchy of the series.  It may be noted the number of series at each level grows exponentially because there are infinite “horizontal” values for each even series and the “vertical” odd number values give rise to corresponding series.

 We may use the above exhibit to explain the convergence of Collatz sequence

• The entire universe of numbers can be constructed starting with 1 and following the above approach.

• The resulting series being geometric, the hierarchy is non-linear, e.g. the even series corresponding to 7, 11 and 17 are child series of the even series corresponding to 13.

• Each multiplication step (3N+1)/2 in Collatz sequence may result in a number with a higher (therefore may appear diverging) but in reality, it moves “vertically upwards” in the above tree exhibit and therefore inches closer to convergence.

• Similarly, each division step (N/2) moves “horizontally leftwards”, closer to convergence.

 7. Conclusion

In conclusion, it may be said that the convergence of Collatz sequence can be explained after reformulating and analysing the problem as elaborated in this document.

Taken at the surface, the upwards and downwards movement of the sequence may appear random; and the eventual convergence to 1 may apparently defy explanation.  However, the reformulation proposed in this document focuses on only on the alternating terminal odd and even values, ignoring the in-between values.  This helps smoothen the noisy variances and reveals the underlying reasons for the convergence as explained.

 

-----------

Annexure

Pathways / Patterns observed in Collatz sequence

While the above approach may explain the convergence, an interesting clue remains unexplored - certain “pathways” towards convergence are much more frequent than others.  Further investigation of this may potentially help restore traceability.  More details on this are included in Annexure.

The analysis presented in the main section of this note limits itself to the first cycle of Oddà Even à Odd.  That analysis suffices to reveal the underlying pattern responsible for conversion.

Progressing to the next cycle (and eventually to conversion) through mathematical equations gets hampered because of the difficulty in converting the powers of 3 (i.e. (6i-5)3ⁿ-1 and (6i-1)3ⁿ-1 to their respective (6i-5)2²ⁿ and (6i-1)2^2n-1 equivalent.

Nonetheless, upon analysis, the following two interesting patterns are evident and may potentially help find a mathematical approach as a further backup to the logical explanation.

 

1. Collatz sequence for 2ⁿ-1 à 3ⁿ-1 series

 

There appears a pattern for higher power values of 2ⁿ-1 to reduce to lower powers.  In some cases (e.g. n=5,6 and n=11,12) there are longer cycles of odd-even-odd conversion before this happens; while in other cases it happens fairly readily.

2-1--> 3-1 --> 2

4-1 --> 9-1 --> 8

8-1 --> 27-1--> 26 --> 8

16-1 --> 81-1 --> 8

32-1 --> 243-1 --> {after several cycles} --> 80 --> 8

64-1 --> 729-1 --> {after several cycles} --> 80 --> 8

128-1 ---> 2187-1--> {after few cycles} --> 26 --> 8

256-1 --> 6561-1 --> {after few cycles} --> 26 --> 8

512-1 --> 19682-1 --> {after few cycles} --> 26 --> 8

 2. From (6i-1)2ⁿ-1; (6i-5)2ⁿ-1 to 2ⁿ-1

 Whichever be the starting number, after a few cycle it discovers the form 2ⁿ-1 / 3ⁿ-1 described.

 If a mathematical proof of #1 and #2 can be found, it could easily lead to the proof of convergence.

 

3. Breaking (2i-1)2ⁿ-1 into four sub-series

If we breakdown (2i-1)2ⁿ-1 into four sub-series, we get distinct patterns for each as described below:

 

Series	Pattern
(8i-7)2n-1	Odd number obtained in cycle 3 for odd n (=2m-1) is identical with the odd number obtained in cycle 2 of  next even n (=2m), e.g.   O3 for  (8i-7)2-1 = O2 for (8i-7)22-1 O3 for  (8i-7)23-1 = O2 for (8i-7)24-1 O3 for  (8i-7)25-1 = O2 for (8i-7)26-1 and so on… O3 for  (8i-7)22m-1-1 = O2 for (8i-7)22m-1
(8i-5)2n-1	Odd number obtained in cycle 3 for even n (=2m) is identical with the odd number obtained in cycle 2 of  next odd n (=2m+1) O3 for  (8i-5)22m-1 = O2 for (8i-5)22m+1-1
(8i-3)2n-1	Even number obtained in cycle 2 for odd n (=2m-1) is identical with the even number obtained in the same cycle 2 of  next even n (=2m) E2 for  (8i-3)22m-1-1 = E2 for (8i-3)22m-1
(8i-1)2n-1	Even number obtained in cycle 2 for even n (=2m) is identical with the even number obtained in the same cycle 2 of  next odd n (=2m+1) E2 for  (8i-1)22m-1 = E2 for (8i-1)22m+1-1

 

In effect, adjacent series merge after either the second or third cycle.  Mathematical illustration (for initial few values of n is provided below).

 

	(8i-7)32n-1-1			(8i-7)32n-1
n	1	3	5	2	4	6
Starting Even	2(12i-11)	2(108i-95)	2(972i-851)	8(9i-8)	8(81i-71)	8(729i-638)
Next Odd (N/2)	12i-11	108i-95	972i-851	9i-8	81i-71	729i-638
Next Even: (3N+1)/2	4(9i-8)	4(81i-71)	4(729i-638)
Next Odd	9i-8	81i-71	729i-638

 

	(8i-5)3n-1				(8i-5)32n+1-1
n	2	4	6	3		5	7
Starting Even	2(36i-23)	2(324i-203)	2(2916i-1823)	8(27i-17)		8(243i-152)	8(2187i-1367)
Next Odd (N/2)	36i-23	324i-203	2916i-1823	27i-17		243i-152	2187i-1367
Next Even: (3N+1)/2	2(27i-17)	2(243i-152)	2(2187i-1367)
Next Odd	27i-17	243i-152	2187i-1367

 

	(8i-3)32n-1-1			(8i-3)32n-1
n	1	3	5	2	4	6
Starting Even	2(12i-5)	2(108i-41)	2(972i-365)	4(9i-7)	4(162i-61)	4(1458i-547)
Next Odd (N/2)	12i-5	108i-41	972i-365	9i-7	81i-61	1458i-547
Next value (3N+2) (once / twice)	18i-7 à 27i-10	162i-61 à 243i-91	1458i-547à 2187i-820	27i-10	243i-91	2187i-820

 

	(8i-3)32n-1-1			(8i-3)32n-1
n	2	4	6	3	5	7
Starting Even	2(36i-5)	2(82i-41)	2(730i-365)	4(54i-7)	4(486i-61)	4(4374i-547)
Next Odd (N/2)	36i-5	82i-41	730i-365	54i-7	486i-61	4734i-547
Next value (3N+2) (once / twice)	54i-7 à 81i-10	486i-61 à 729i-91	4374i-547à 6561i-820	81i-10	729i-91	6561-820

 

We can use the above property to further reduce the set of numbers that need to be examined for convergence as shown in the below exhibit.   As the even powered series (2i-1)2²ⁿ-1 merges with the odd powered series – either (2i-1)2^2n-1-1 or (2i-1)2²ⁿ⁺¹-1, it would suffice to consider only the odd powered series (2i-1)2^2n-1-1 for further analysis.

Additionally, as we have seen earlier, values of (2i-1) that are divisible by 3 (i.e. 6i-3) yield duplicated values.  Therefore, we may ignore those as well.   This requires us to further breakdown the subseries as follows:

8i-7 à 24i-23, 24i-7 (ignoring 24i-15);

8i-5 à 24i-13, 24i-7 (ignoring 24i-21)

8i-3 à 24i-19, 24i-11 (ignoring 24i-3)

8i-1 à 24i-17, 24i-1 (ignoring 24i-9)

 

 Together, these four sub-series would bring us back to the original (6i-5) and (6i-1) as root multipliers.

 To summarize, we may consider only the odd powered series of (6i-5) and (6i-1); i.e. (6i-5)2^2n-1 and (6i-1)2^2n-1 for further investigations.