## 9.8.16

### Powers of Collatz Part 1

I recently stumbled onto the Collatz Conjecture, which states that any n iterated through the algorithm below will eventually be reduced to 1:

Given an integer n, then either divide n by 2 if n is even or multiply n by 3 and add 1 if n is odd.

Example: Let n=42, which is even so divide by 2 and n = 21, which is odd so 3*21+1 = 64, which is even so n = 64/2=32, which is even so n = 32/2=16, which is even so n = 16/2=8, which is even so n = 8/2=4, which is even so n = 4/2=2, which is even so n = 2/2=1, which generates the following:
42->21->64->32->16->8->4->2->1.

To me the most curious thing about it is the fact that shortly before it reaches 1, it hits a bunch of consecutive powers of 2.

And so does the (n+1)/2 row of the exponentiation table of Zn. In fact, 42->21->64->32->16->8->4->2->1 vaguely resembles all unique consecutive powers of 43 mod 85, namely 43->64->32->16->8->4->2->1

It might just be a wishful coincidence but it feels like powers of 2 are being generated backwards in some finite field(s) somehow as this algorithm hits an odd integer.

Update:  42->21->64->32->16->8->4->2->1 are the last few terms of the sequence of unique powers of (n+1)/2 for n = 107 since (107+1)/2 = 54 then all unique consecutive powers of 54 mod 107 are:

54,27,67,87,97,102,51,79,93,100,50,25,66,33,70,35,71,89,98,49,78,39,73,90,45,76,38,19,63,85,96,48,24,12,6,3,55,81,94,47,77,92,46,23,65,86,43,75,91,99,103,105,106,53,80,40,20,10,5,56,28,14,7,57,82,41,74,37,72,36,18,9,58,29,68,34,17,62,31,69,88,44,22,11,59,83,95,101,104,52,26,13,60,30,15,61,84,42,21,64,32,16,8,4,2,1

Another interesting observation is that 107 is in fact a tough prime. Below is an implementation of the algorithm for generating powers of 2 backwards.

On a slightly different note, to me this is very interesting as I recently made the following observation that I haven't publicly posted about because I haven't been able to prove it in connection to a different problem.

Claim: Given any odd integer n and k = (n-1)/2 then 3k + 1 = k mod n

Proof: (3((n-1)/2) + 1) mod n
(2(n-1)/2) mod n + ((n-1)/2) mod n + 1 mod n
= (n-1) mod n + ((n-1)/2) mod n + 1 mod n
= n mod n + (-1) mod n ((n-1)/2) mod n + 1 mod n
((n-1)/2) mod n + (1-1) mod n  // since n mod n = 0 mod n
((n-1)/2) mod n

.'.

Similarly, it can be shown that given any odd integer n and k = (n+1)/2 then 3k + 1 = k+2  mod n

I already discussed how unique consecutive powers of 2 mod n are essentially all unique consecutive powers of (n+1)/2 backwards and I also conjectured that every consecutive even power of (n-1)/2 is equal to every consecutive even power of (n+1)/2 and the sum of every odd power of (n-1)/2 and (n+1)/2 is equal to n, at least when n is the product of distinct odd primes.

I'll try to illustrate what I mean with an example.

Example: Let n = 35 so (n-1)/2 = 17 and (n+1)/2 = 18
The 17th and 18th rows of the exponentiation table of Z35 are circled below

Note that 172 mod 35 = 182 mod 35 = 9 mod 35
Also 174 mod 35 = 184 mod 35 = 11 mod 35
and so on for all even powers of 17 and 18 whereas
173 + 183 mod 35 = 35
and 175 + 185 mod 35 = 35
and so on for all odd powers of 17 and 18 mod 35

I always imagine that there is some kind of an underlying cycle that connects the (n+1)/2 and (n-1)/2 rows of the exponentiation table of Zbut this might be just wishful thinking to put it mildly.