Collatz Conjecture Proof

The Collatz conjecture is one of the most famous unsolved problems in mathematics. This conjecture states that starting with any positive integer, repeatedly applying the two simple rules – "if even, divide by 2; if odd, multiply by 3 and add 1" will eventually lead to 1. Despite various approaches and attempts, the Collatz Conjecture     remains unproven for no general proof has been found. Most of the researches are focus on put the two simple operation together, but what will happen if separate the two operation, and hold the divided by 2 for a while?

     If a positive integer D after n "multiply by 3 and add 1(odd-step)" and m     "divide by 2(even-step)" turn to 1, this can be expressed as:

        D𝐧+Y𝐧=2^𝐦                 [1]

    where 𝐷𝐧=3^𝐧?𝐷. For any positive integer D, if such Yn existed based on     Collatz Conjecture iteration, Collatz Conjecture should be true. Now what is needed to do is trying to figure out how Y is built up along with Collatz Conjecture iteration and such Y𝐧 exist.

For any positive integer D can be expressed as the product of 2 to the power of k(0) and an odd number:

            D=2^k(0)(Q?2+1)     k(0)=0,1,2,3,…     [2]

Now we can apply Collatz Conjecture iteration to the odd part and collect the divided by 2 and put it to the 2^k part. Any odd number to another odd number, one odd-step and one or more even-step needed. For example:

(1) Number 3:

   3*3 + 1 = 10 → 5,

   one odd-step and one even-step, collect one divided by 2 → 2k(0)+1

(2) Number 9:

   3*9 + 1 = 28 →14 →7,

   one odd-step and two even-steps, collect two divided by 2 → 2k(0)+2

(3) Number 13:

   3*13 + 1 = 40 →20 →10 → 5,

   one odd-step and three even-steps, collect three divided by 2 → 2k(0)+3

(4) Number 37:

   3*37 + 1 = 112 → 56 → 28 → 14 → 7,

   one odd-step and four even-steps, collect four divided by 2 → 2k(0)+4

Generally for Equation [2], just apply 3n+1 and divided by 2 to the odd part (Q*2 + 1) and pass divided by 2 to 2^k portion we got:

          2^k(0)[3(Q?2+1)+1]

        =3?[2^k(0)(Q?2+1)]+ 2^k(0)

        =3?D+ 2^k(0)        collect 𝑘(0)             [3]

        = D₁+ Y₁         D₁= 3¹?D,Y₁= 2^k(0),D1> Y1

in other way,

          2^k(0)[3(Q?2+1)+1]

        =2^k(0)[3?Q?2+4]

        =2^k(0)+1[3?Q+2]

        =2^k(0)+1?2^x?(Q₁?2+1)

        =2^k(0)+(1+x)?(Q₁?2+1)     collect 1+x,x=0,1,2,3,…

        =2^k(1)?(Q₁?2+1)        k(1)=k(0)+(1+x)       [4]

after one 3n+1 and one or more divided by 2 we got a new equation from Equation [2]:

        D₁+ Y₁= 2^k(1)?(Q₁?2+1)    k(1)>k(0)          [5]

Compare to Equation [2]:

        D→D₁+Y₁,2^k(0)→2^k(1)=2^{𝑘(0)+(1+𝑥)},Q→ Q1

Apply another 3n+1 and divided by 2 to the odd part (Q1*2 + 1) of Equation [5] we got:

         2^k(1)[3(Q₁?2+1)+1]

        =3?[2^k(1)(Q₁?2+1)]+2^k(1)

        =3?D₁+3?Y₁+2^k(1)

        =D₂+Y₂         D₂=3²?D,Y₂=3?Y₁+2^k(1)

in other way,

         2^k(1)[3(Q₁?2+1)+1]

        =2^k(1)[3?Q₁?2+4]

        =2^k(1)+1[3?Q₁+2]

        =2^k(1)+(1+x)(Q₂?2+1)     collect 1+x,x=0,1,2,3,…

        =2^k(2)(Q₂?2+1)         k(2)>k(1)

same as Equation [5] we got 

        D₂+Y₂ = 2^k(2)(Q₂?2+1)

repeat the 3n+1 and divided by 2 on the odd part to step n we could get:

        D_n+Y_n=2^k(n)(Q_n?2+1)             [6]

The above process could be interpreted as it approaches a certain pure even-x number 2^m with continuing iteration, then we can get the following equation by combining Equation [1] and [6]:

        2^𝐦?𝟏n+Y_n=2^k(n)(Qn?2+1)≤2^𝐦         [7]

let Y₀ = 0, then

        Y₁=2^k(0)=3?Y₀+2^k(0)

it can be figured out that Y is built up as:

    Y₀=0,Y₁=3?Y₀+2^k(0),Y₂=3?Y₁+2^k(1),…,Y_n=3?Y_n?1+2^k(n?1)

    k(0) < k(1) < ... < k(n-1) < k(n)

The minimum step of k is 1, and for any odd number k(0) = 0, the minimum k sequence should be:

    k = 0, 1, 2, 3, ...

and the minimum Y sequence is as:

    Y = 0, 1, 5, 19, 65, 211, ..., 3n - 2n.

As described above, D and Y are both multiplied by 3, D is not changed, but Y is added 2^k each time, so that Y is getting bigger and bigger. At the beginning Y₁1, along with the iteration continuing, Y will exceed D and turn to Y > D from Y ≤ D at certain step. D_n is changed linearly and Y_n is growing up along with multiply by 3 and add 2^k.

Assuming Yn-1 ≤ Dn-1 at step n-1, and Yn>Dn at step n, from Equation [7] we got:

        2^𝐦?𝟏n+Y_n=D_n+3?Y_n?1+2^k(n?1)≤2𝐦         [8]

        2^𝐦?𝟏n+3?Y_n?1+Δ_n=2^𝐦              [9]

To ensure from Yn-1 ≤ Dn-1 to Yn>Dn, 2^k(n-1) (difference between D_n and 3*Y_n-1) must take the possible maximum value. From Equation [8], the maximum value of 2^k(n-1) could be 2^m-1. But if 2^k(n-1) = 2^m-1, D_n + 3*Y_n-1 should be ≤ 2^m-1, and result in 3*Y_n-1 = 0 and D_n = 2^m-1. For Y_n-1 can not be 0, so that 2^k(n-1) must be less than 2^m-1, and the maximum possible value should be 2^m-2. so we got:

        2^𝐦?𝟐≤Dn<2^𝐦?𝟏

        2^𝐦?𝟐≤3?Y_n?1<2^𝐦?𝟏

        2^𝐦?𝟏n+3?Y_n?1≤2^𝐦

From above analysis we can get: 

        Δ_n=2^{𝐤(𝐧?𝟏)}=2^𝐦?𝟐

so that

        3?Y_n?1+Δ_n=3?Y_n?1+2^{𝐤(𝐧?𝟏)}=Y_n

Due to Y_n satisfied Equation [1] exist for any positive integer, so that Collatz Conjecture should be TRUE for any positive integer.

Base-X Conjecture and Collatz Conjecture Proof