# Collatz Sequence – part 5

**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 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^{n}, 2^{n-1}, 2^{n-2}, …, 2^{2}, 2^{1}, 2^{0}

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_{1} = { n = 2p / n < 10}

P_{2} = { n = 2p / n 10, p = 2 + 3k k ∈ ^{*}}

P_{3} = { n = 2p / n 10, p = 3 + 3k k ∈ ^{*}}

P_{4} = { n = 2p / n 10, p = 4 + 3k k ∈ ^{*}}

P = P_{1} P_{2} P_{3} P_{4}

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_{2} are given by suite ρ_{2,k} = 6k + 4 with k ∈ ^{*}.

Numbers in P_{3} are given by suite ρ_{3,k} = 6k + 6 with k ∈ ^{*}..

Numbers in P_{4} 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_{2}) = 3k + 2 with k ∈ ^{*}, which is when k is , and when k is .

η_{3,k}(P_{3}) = 3k + 4 with k ∈ ^{*}, which is when k is , and when k is .

η_{4,k}(P_{4}) = 3k + 8 with k ∈ ^{*}, which is when k is , and when k is .

### Which partitions hold numbers that are power of 2

P_{2} = 6k + 4 = 2 (3k + 2) = 2^{n} 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^{n} – 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_{4} = 6k + 8 = 2 (3k + 4) = 2^{n} with k and n ∈ ^{*}.

Practicing this suite, it is easy to find k for a given n. Just compute numerically function (2^{n} – 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_{3} = 6k + 6 = 2 (3k + 3) = 2^{n} 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_{2} generates all the power of 2, with exponent being , starting from 4 and P_{4} generates all the power of 2, with exponent being , starting from 5. Since P_{1} 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 ∈ P_{2} 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 ∈ P_{4}.

**Fourth important result**

This proves that all antecedents of P_{2} come from P_{4}. 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_{2}

P_{2} 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

**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.