Neonira
by Neonira

Categories

  • mathematics
  • EN

Tags

  • mathematics
  • R
  • computing

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

  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

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 collatz 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

  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.

υ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

  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 nth result, directly from the input.

For numbers, it is quite obvious, as ηk = η1 / 2k 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 = 3k φ1
  • σk = Σi = 1k 3i - 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 3k 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 + 3n

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