Collatz Sequence – part 5

[This article was first published on NEONIRA, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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 22(q + 1) with q. Thus the condition that the exponent of 2 being is sufficient.

ωn = ( ωn+1 – 1) / 3 = (22(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 2n, 2n-1, 2n-2, …, 22, 21, 20

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
P1 = { n = 2p / n < 10}
P2 = { n = 2p / n 10, p = 2 + 3k k ∈ *}
P3 = { n = 2p / n 10, p = 3 + 3k k ∈ *}
P4 = { n = 2p / n 10, p = 4 + 3k k ∈ *}
P = P1 P2 P3 P4

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 P2 are given by suite ρ2,k = 6k + 4 with k*.

Numbers in P3 are given by suite ρ3,k = 6k + 6 with k*..

Numbers in P4 are given by suite ρ4,k = 6k + 8 with k*.

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

η2,k(P2) = 3k + 2 with k*, which is when k is , and when k is .

η3,k(P3) = 3k + 4 with k*, which is when k is , and when k is .

η4,k(P4) = 3k + 8 with k*, which is when k is , and when k is .

Which partitions hold numbers that are power of 2

P2 = 6k + 4 = 2 (3k + 2) = 2n with k and n*. Solution is the suite OEIS® A020988 defined by kp = (2 / 3) * 4p-1 with p 3.

Practicing this suite, it is easy to find k for a given n. Just compute numerically function (2n – 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

P4 = 6k + 8 = 2 (3k + 4) = 2n with k and n*.

Practicing this suite, it is easy to find k for a given n. Just compute numerically function (2n – 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

P3 = 6k + 6 = 2 (3k + 3) = 2n 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 P2 generates all the power of 2, with exponent being , starting from 4 and P4 generates all the power of 2, with exponent being , starting from 5. Since P1 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 ω.

ω2 = 3 ω1 + 1 = 3 i + 1 = 3 (i – 1) + 4 = 6 k + 4 ∈ P2 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 ω2. Instead of dividing by 2, I’ll multiply by 2. This brings

inv(η)3 = 2 * ω2 = 2 * (6k + 4) = 12 k + 8 = 6 2k + 8 ∈ P4.

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

Collatz sequence study for starting number in P2

P2 is . So, I’ll apply η.

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

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

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

η4 = ω3 / 2 = (9k + 7) / 2

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

η6 = ω3 / 2 = (27k + 23) / 4

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

η8 = ω3 / 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

To leave a comment for the author, please follow the link and comment on their blog: NEONIRA.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)