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

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

1. the parity of q when p is
2. 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

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.

So, we have proven several things, for numbers

1. 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.
2. 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.

So, are now proven several things, for numbers

1. 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.
2. 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 = η₁ / 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 φ₁
• σ_k = Σ_{i = 1}^k 3^{i – 1}.

Parity analysis

parity analysis of η_k

As η_k starts forcibly with η₁ 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 φ₁ 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ⁿ

> 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(φ₁) and parity(φ_{2 n}) = ¬ (parity(φ₁)).

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.