# Collatz Sequence – part 2

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

On first post part , we got some intuition about Collatz sequence], that seems to be unproven yet. Let’s try to prove it mathematically.

## Some mathematic reminders

### Canonical form a a natural integer

We name canonical form any natural integer n, written under one of following forms

- n = 10 t + u
- n = 100 h + 10 t + u

Note that n, h, d, u ∈ ℕ where h represents hundreds, t represents tens, and u to represents units.

Unless otherwise specified, the expression canonical form refers always to the first form.

### Determining parity of a number

By definition, an number n can be written as n = 2 p n, p ∈ ℕ note that n is , but we have no information about p that can be or .

By definition, an numbern can be written as n = 2 p + 1 n, p ∈ ℕ note that n is , but we have no information about p that can be or .

#### Parity of a sum of two natural integers

Using the shown definitions, I can demonstrate following table of truth for parity addition of two natural integers

sum p + q | p is | p is |

q is | sum is | sum is |

q is | sum is | sum is |

So, given one number p, to determine the parity of the sum with q, we just have to consider

- the parity of q when p is
- the negation of the parity of q, that is ¬q, when p is

#### Parity of a product of two natural integers

Using the shown definitions, I can demonstrate following table of truth for parity multipliction of two natural integers

multiplication p * q | p is | p is |

q is | multiplication is | multiplication is |

q is | multiplication is | multiplication is |

So, the production of two natural numbers is only when both of them are .

## Digit mutation proof

Remember Collatz sequence definition

### Digit mutation proof for numbers

In this part, as all numbers are , I will apply division by 2.

υ_{n} | result of Collatz rule application | ||||

canonical form | digit | parity | calculus formula | canonical form | digit |

10 t + 0 | 5 t | 10 p + 0 t = 2 p 10 p + 5 t = 2 p + 1 | 0 when d is 5 when t is | ||

10 t + 2 | 5 t + 1 | 10 p + 1 t = 2 p 10 p + 6 t = 2 p + 1 | 1 when t is 6 when t is | ||

10 t + 4 | 5 t + 2 | 10 p + 2 t = 2 p 10 p + 7 t = 2 p + 1 | 2 when t is 7 when t is | ||

10 t + 6 | 5 t + 3 | 10 p + 3 t = 2 p 10 p + 8 t = 2 p + 1 | 3 when t is 8 when t is | ||

10 t + 8 | 5 t + 4 | 10 p + 4 t = 2 p 10 p + 9 t = 2 p + 1 | 4 when t is 9 when t is |

So, we have proven several things, for numbers

- When applying Collatz sequence to an number, produced result will fork on two different digits depending of the parity of t. Note, the special case of 0, that is the only case with self loop.
- As we divide, by 2, the result is strictly less than the input.

### Digit mutation proof for numbers

In this part, as all numbers are , I will apply apply by 3 υ_{n} + 1.

υ_{n} | result of Collatz rule application | ||||

canonical form | digit | parity | calculus formula | canonical form | digit |

10 t + 1 | 30 t + 4 | 10 (3 t) + 4 | |||

10 t + 3 | 30 t + 10 | 10 (3 t + 1) + 0 | |||

10 t + 5 | 30 t + 16 | 10 (3 t + 1) + 6 | |||

10 t + 7 | 30 t + 22 | 10 (3 t + 2) + 2 | |||

10 t + 9 | 30 t + 28 | 10 (3 t + 2) + 8 |

So, are now proven several things, for numbers

- When applying Collatz sequence to an number, produced result will always be an number. This implies that when applying Collatz sequence, we will never apply twice in a run the Collatz sequence rule.
- The result is always greater than the input for numbers

## Suite analysis

Let’s focus now on suite analysis, has this will bring many insights on the Collatz Sequence results.

### Suite definitions

Let’s divide the Collatz sequence into two independent suites, for analysis convenience.

First suite is for numbers: ω_{n + 1} = 3 ω_{n} + 1

Second suite is for numbers:

η_{n + 1} = η_{n} / 2

By convention, the indice _{n} starts at 1.

### Calculus formulaes

We need a formulae that provides the n^{th} result, directly from the input.

For numbers, it is quite obvious, as

η_{k} = η_{1} / 2^{k} with k being the number of times we apply the transformation, will provide the result.

For numbers, suite analysis will show that

ω_{k} = φ_{k} + σ_{k}

- with φ
_{k}= 3^{k}φ_{1} - σ
_{k}= Σ_{i = 1}^{k}3^{i – 1}.

### Parity analysis

#### parity analysis of η_{k}

As η_{k} starts forcibly with η_{1} being , the recurring process of division by 2 repeats while η_{k} is and stops immediately when not. In the worst case, we execute a single division by 2.

#### parity analysis of ω_{k}

As this suite is composed of the sum of 2 suites, we will use the addition parity table.

##### parity analysis of φ_{k}

As φ_{k} starts forcibly with φ_{1} being , the recurring process of multiplication by 3^{k} that is always too, brings always an result.

##### parity analysis of σ_{k}

The suite σ_{n} results from a sum. The suite is the sum of the successive power of 3, and so σ_{n + 1} = σ_{n} + 3^{n}

```
> p <- 0:16
> z <- 3^p
> sapply(p[-1], function(e) sum(z[1:e]))
[1] 1 4 13 40 121 364 1093 3280
[8] 9841 29524 88573 265720 797161 2391484 7174453 21523360
```

**CURIOSITY**: Seems that each forth numbers are multiple of 10.

σ_{4n + 1} ends with digit

σ_{4n + 2} ends with digit

σ_{4n + 3} ends with digit

σ_{4n + 4} ends with digit

Sum of this four ending digits turns to be 20.

So the parity of suite σ_{n} follows a pattern that is

and then , and repeat this sequence.

More precisely, we have parity(φ_{2 n + 1}) = parity(φ_{1}) and parity(φ_{2 n}) =

¬ (parity(φ_{1})).

Therefore, the suite ω_{n} that is the addition of 2 suites, φ_{n} that is always and σ_{n} that is an alternate parity suite starting with an value.

In short, ω_{n} has the same parity as σ_{n}.

### Digit mutation conclusion

The canonical forms used on paragraphs 2.1 and 2.2, covers individually all the numbers that end with a digit from to . They form a partition of ℕ. This partition is fully covering ℕ as each number ends by one of the 10 digits.

One way to understand the digit mutation tables, is to consider the canonical form as a generative suite of the input number, and applying η or ω will create a generative suite of the output number that will end with a predicted digit.

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