[seqfan] This sequence proves the Collatz Conjecture

[Ali Sada]

Hi everyone,
The usual Collatz algorithm loses data. For example, 11, 22, 44, 88, ... are all the same number,11. In my analysis, this data is preserved in a sequence. 22 becomes 45, 44 becomes 181, 88 becomes 725, etc. 
With that approach, and by rearranging odd numbers in a certain array, the Collatz pattern becomes very easy to detect. By using the sequence and the array, we can see clearly that by applying 3m+1 multiple times we reach A002450, and that proves the Collatz. 


Thank you all for your responses.  

Best,
Ali 

     
 

Please note that since I have a severe problem with notations, sometimes I will explain with numbers. The rules could be generalized for any range.

I will use the terms below in the coming text:

A1 is A002450 (a(n) = (4^n-1)/3

A2 is A072197 (a(n) = 3+ 10* (4^(n-1)-1)/3)

A3 is A096773, a combination of A1 and A2, starting with 3.

3, 1, 13, 5, 53, 21, 213, 85,…

A4 is A079319 (a(n) = 2^n + (4^n-1)/3)

m is an odd positive integer.

n, i, j, l, k, t, q are positive integers.

E is an even positive integer

O is an odd positive integer

The I operation, or I(m), means 3*m+1

The R operation, or R(m), means 4m+1

To start the proof, I will use the word “equivalent” to refer to the relationship between m, 4m+1, 4(4m+1)+1, etc.

For example, in the Collatz world, 7, 29, 117, 469, …are all equivalent to each other.

7*3+1 = 22, 22/2 = 11

29*3+1 = 88, 88/8 =11

117*3+1= 352, 352/32 = 11

(Say m=2k+1. I(m) = 6k+4. 4m+1 = 8k+5. I(8k+5) = 3*(8k+5)+1 = 24k+16 and when we divide by 4 we also get 6k+4)

Then, we define the following operation, let’s call it Operation “A”:

If E is an even number, we write it in this form O * 2^k

To obtain A(E), we repeat the operation R on O k times.

For example to find 8 =1 * 2^3, so, to find A(8), we repeat R on 1 three times

1*4+1 = 5, 5*4+1 = 21, 21* 4+1 = 85. So, A(8) = 85.

Another example, 60 = 15 *2*2, to find A(60), we repeat R on 15 twice

15*4+1 = 61, 61*4+1 = 245. So, A(60) = 245.

Now, we define the IA operation, which is a combination of the I operation and the A operation, in this order.

IA(m,t) means we repeat the IA operation t times.

For example, IA(7,3) is done line this

7*3+1 = 22, A(22) = 45, 45*3+1 = 136, A(136) = 1109, 1109*3+1 = 873813

So, IA(7,3) = 87813.

 

To construct the main sequence in this analysis, let’s call it S(n), we take the positive integers sequence and replace each even number with its A form. Odd numbers remain the same.

We get:

1, 5, 3, 21, 5, 13, 7, 85, 9, 21, 11, 53, 13, 29, 15, 341,…

 

Now, if we can prove that applying the IA operation on any odd number would lead eventually to A1, then the Collatz conjecture is proven. And since A2 is one step away from A1 (Collatz-wise), then the conjecture is proven if m reaches A3 through multiple IA operations. 

 

To do that, let’s put all odd numbers in an array, let’s call H(i,j).

The first column is numbers congruent to A3(j) (mod 2^(j+1))

The first column will be numbers congruent to 3 (mod 4)

3, 7, 11, 15, 19, 23, ……

The second column will be numbers congruent to 1 (mod 8)

1, 9, 17, 25, 33, …

The third column will be numbers congruent to 13 (mod 16)

13, 29, 45, 61, …

And so on.In Summary, we want to prove that m, after multiple IA operations, will reach the top of a column in the H array.
 

Now if we apply the IA operation one time on H(i,j)

IA(H(i,1)) = 3 * 2^j + A4 = 3 * 2^j + 2^j + (4 ^ j-1)/3 …………(1)

Let’s call it Equation 1.

For example, if we apply the IA operation in the first column we get 6 * H(i,1) +3, and if we we apply the IA operation on the second column we get 12*H(i,2) + 9, and so on.

 

To prove that all off numbers will reach A3 if we apply the IA operation enough times, let’s take the odd numbers in the range between 2^k and 2^(k+1)

When we apply the IA operation once, each number “jumps” to the left, based on Eq. 1.

There are two important numbers here.

D is the difference between IA(m,1) and the largest A3 term that is less than IA(m,1).

For example, when we apply the IA on 33 once, we get 405. The largest A3 term smaller than 405 is 341. So, D(IA(33,1)) = 405-341 = 64.

The second number is d, which is the number of A3 terms that m jumps over after one IA operation.

For example, after one IA operation, 33 jumps over 53, 85, 213, and 341. So, d(IA(33,1)) = 4 

The highest jump will be for the members of A3 in the group, let’s call them “Qabsus” (centers in Akkadian).

Between 2^k and 2^(k+1), the qabsu is (4^((k-1)/2)-1)/3 if k is odd, and 3+ 10* (4^(k/2)-1/3) if k is even, where k1 = k/2 if k is even, and k1=(k-1)/2 if k is odd.

 

For example, let’s take the odd numbers in the range between 32 and 64. The qabsu is 53.

For this range, the highest qabsu belongs to 53. D(IA(53,1))= 5461-3413= 2048. In general, D(q) = 2^(2k+1). And in each IA iteration, k increases to 2k+2 if k is odd, and 2k+4 if k is even.  

As for d(q), it is k+2 for any k.

For all other numbers in the range, k, D and d increase, but less than k(q), D(q) and d(q) respectively.

However, in each iteration, d increases compared to its range. For example,

IA(27,1) = 165 and IA(27,2)= 8021 .  k increased from 4 to 7, to 13. This rate of change will increase, slowly but surely, until it reaches the rate of A3 terms.

 

The same thing with D. It was 6 (2*3) , then it became 80 (5*16), then it became 2560 (5*512).  This will continue with each iteration, and eventually D must become a “pure” power of 2 and joins A3.

 

d also has no other option but to increase until it reaches a range between 2^kf and 2^(kf+1) where its growth reaches the same level as A3 terms.

 

Best,

 

Ali