Collatz Sequence – part 5

Find previous posts if you haven’t yet read them. first post, second post, third post, and fourth post.

Numerical approach for number made of 1 unique digit

First important result
All the numbers from 1 to 9, provides 1 as final output of Collatz sequence. This could be easily demonstrated numericaly, just by applying Collatz rule in sequence for each number.

Reverse analysis

Instead of starting from any number and applying Collatz sequence, let’s do the exact opposite. I’ll start from number 1, and will find its antecedents, and apply same logic on those ones.

Case of number 1

1 is an number. Therefore it can only result from a division by two, applying η a.
So its unique antecedent is 2.

Case of number 2

2 is an number. Therefore it can only result from two distinct sources, applying ω or η b.
But ω is not applicable as 3 * number + 1 is 4 in ^*.
Therefore only antecedent of 2 is to be given by η, which gives 4.

Case of number 4

4 is an number. So b applies.
Applying ω gives 1.
Applying η gives 8.
We have two antecedents, but the first one is also the stopping condition, that has already been studied.

Case of number 8

8 is an number. So b applies.
Applying ω gives a result that is not in .      (8 – 1) / 3 = 7 / 3 .
Applying η gives 16.
We have one antecedent, that is 16.

ω analysis

What are the conditions for ω to bring a result in , considering an input in ?

ω_{n + 1} = 3 ω_n + 1     by definition

ω_n = ( ω_n+1 – 1) / 3

Therefore a condition to find an antecedent of a number p by ω is that p – 1 is multiple of 3.

Given that p is a power of 2, following logic expressed previously in this post, then the only possibility for ω_{n + 1} to be dividable by 3, it to be of the form 2^{2(q + 1)} with q ∈ . Thus the condition that the exponent of 2 being is sufficient.

ω_n = ( ω_n+1 – 1) / 3 = (2^{2(q + 1)}– 1) / 3

> z <- 0:20
> omega <- 2^z
> omega
 [1]       1       2       4       8      16      32      64     128     256 
 [10]	 512    1024    2048    4096    8192   16384   32768   65536	131072
 [19] 262144  524288 1048576
> previous <- (omega - 1) / 3
> previous
 [1]  0.000000e+00 3.333333e-01 1.000000e+00 2.333333e+00 5.000000e+00 1.033333e+01
 [7]  2.100000e+01 4.233333e+01 8.500000e+01 1.703333e+02 3.410000e+02 6.823333e+02 
 [13] 1.365000e+03 2.730333e+03 5.461000e+03 1.092233e+04 2.184500e+04 4.369033e+04 
 [19] 8.738100e+04 1.747623e+05 3.495250e+05
> p <- which(previous %% 1 == 0)
> p
 [1]  1  3  5  7  9 11 13 15 17 19 21
> z[p]
 [1]  0  2  4  6  8 10 12 14 16 18 20

Second important result
There is one and only one suite of numbers in Collatz sequence, that leads to stopping condition i.e. reaching 1that is the suite 2ⁿ, 2^n-1, 2^n-2, …, 2², 2¹, 2⁰

The typical converging sequence if then finished by number suite: 16, 8, 4, 2, 1. It is important to note here, that 16 ends with and belongs to cluster 1, that 8 ends with and belongs to cluster 2, whereas all the remaining numbers of this suite, belong to cluster 3. Refer to previous posts, if you need.

Corollary
If a Collatz sequence generated or stating number is a power of 2, then convergence to 1 is proven.

Convergence analysis

I will now show, that whatever the number considered, Collatz sequence converges. To do so, I will partition .

Given following definitions
P₁ = { n = 2p / n < 10}
P₂ = { n = 2p / n 10, p = 2 + 3k k ∈ ^*}
P₃ = { n = 2p / n 10, p = 3 + 3k k ∈ ^*}
P₄ = { n = 2p / n 10, p = 4 + 3k k ∈ ^*}
P = P₁ P₂ P₃ P₄

So P is a partition of all numbers from .

> k <- 1:20
> p2 <- 2 * (2 + 3 * k)
> p3 <- 2 * (3 + 3 * k)
> p4 <- 2 * (4 + 3 * k)
> p2
 [1]  10  16  22  28  34  40  46  52  58  64  70  76  82  88  94 100 106 112 118 124
> p3
 [1]  12  18  24  30  36  42  48  54  60  66  72  78  84  90  96 102 108 114 120 126
> p4
 [1]  14  20  26  32  38  44  50  56  62  68  74  80  86  92  98 104 110 116 122 128

Numbers in P₂ are given by suite ρ_2,k = 6k + 4 with k ∈ ^*.

Numbers in P₃ are given by suite ρ_3,k = 6k + 6 with k ∈ ^*..

Numbers in P₄ are given by suite ρ_4,k = 6k + 8 with k ∈ ^*.

Since all are these numbers are , then let’s apply η to them.

η_2,k(P₂) = 3k + 2 with k ∈ ^*, which is when k is , and when k is .

η_3,k(P₃) = 3k + 4 with k ∈ ^*, which is when k is , and when k is .

η_4,k(P₄) = 3k + 8 with k ∈ ^*, which is when k is , and when k is .

Which partitions hold numbers that are power of 2

P₂ = 6k + 4 = 2 (3k + 2) = 2ⁿ with k and n ∈ ^*. Solution is the suite OEIS® A020988 defined by k_p = (2 / 3) * 4^p-1 with p 3.

Practicing this suite, it is easy to find k for a given n. Just compute numerically function (2ⁿ – 4) / 6 for values of n, starting from 4.

> f <- function(n) (2^n - 4) / 6
> k <- f(2 * 2:12)
> k
 [1]       2      10      42     170     682    2730   10922   43690  174762
[10]  699050 2796202
> p2 <- 2 * (3 * k + 2)
> p2
 [1]       16       64      256     1024     4096    16384    65536   262144
 [9]  1048576  4194304 16777216
> n <- log(p2) / log(2)
> n
 [1]  4  6  8 10 12 14 16 18 20 22 24

P₄ = 6k + 8 = 2 (3k + 4) = 2ⁿ with k and n ∈ ^*.

Practicing this suite, it is easy to find k for a given n. Just compute numerically function (2ⁿ – 8) / 6 for values of n, starting from 5.

> g <- function(n) (2^n - 8) / 6
> k <- g(2 * 2:12 + 1)
> k
 [1]       4      20      84     340    1364    5460   21844   87380  349524
[10] 1398100 5592404
> p4 <- 2 * (3 * k + 4)
> p4 
 [1]       32      128      512     2048     8192    32768   131072   524288
 [9]  2097152  8388608 33554432
> n <- log(p4) / log(2)
> n
 [1]  5  7  9 11 13 15 17 19 21 23 25

P₃ = 6k + 6 = 2 (3k + 3) = 2ⁿ with k and n ∈ ^*. This equation has no solution because 2 and 3 are primes and therefore no power of 2 can be expressed as the result of a multiplication by 3.

Third important result
I have now shown that P₂ generates all the power of 2, with exponent being , starting from 4 and P₄ generates all the power of 2, with exponent being , starting from 5. Since P₁ contains values 2, 4 and 8, the partition covers all the power of 2, for exponent greater or equal to 1.

Collatz sequence relation to partition

Let’s consider any number i 9. This number is the input to the Collatz sequence.

As it is , I apply ω.

ω₂ = 3 ω₁ + 1 = 3 i + 1 = 3 (i – 1) + 4 = 6 k + 4 ∈ P₂ because i – 1 is forcibly and so can be expressed as i – 1 = 2 k

Now let’s apply inverse inv(η) to find the antecedent of ω₂. Instead of dividing by 2, I’ll multiply by 2. This brings

inv(η)₃ = 2 * ω₂ = 2 * (6k + 4) = 12 k + 8 = 6 2k + 8 ∈ P₄.

Fourth important result
This proves that all antecedents of P₂ come from P₄. So, proving Collatz convergence for one or the other will be sufficient to prove Collatz sequence converges.

Collatz sequence study for starting number in P₂

P₂ is . So, I’ll apply η.

η₂ = i / 2 = (6 k + 4 ) / 2 = 3 k + 2.

Let’s consider k as . So, I will apply in sequence ω and η.

ω₃ = 3 (3 k + 2) + 1 = 9 k + 7

η₄ = ω₃ / 2 = (9k + 7) / 2

ω₅ = 3 ((9 k + 7) / 2)+ 1 = (27k + 23) / 2

η₆ = ω₃ / 2 = (27k + 23) / 4

ω₇ = 3 ((27 k + 23) / 4)+ 1 = (81k + 73) / 4

η₈ = ω₃ / 2 = (81k + 73) / 8

> constant <- function(n) {
+   if (n == 1) return(2)
+   3 * constant(n - 1) + if (n > 2) 2^(n - 2) else 1
+ }
> sapply(1:20, constant)
 [1]          2          7         23         73        227        697
 [7]       2123       6433      19427      58537     176123     529393
[13]    1590227    4774777   14332523   43013953  129074627  387289417
[19] 1161999323 3486260113