Powers of Collatz Part 2

In my previous blog entry I talked about how The Collatz Conjecture might have something to do with generating powers of (n+1)/2 mod n, especially when n is the product of distinct primes.

I conjecture that the algorithm behind The Collatz Conjecture always reaches some power of (n+1)/2 mod n for some n, and this power is not necessarily a power of 2 in Z.

So what happens when the algorithm behind the Collatz conjecture is applied to (n+1)/2 starting from ((n+1)/2)² mod n?

Powers of Collatz Algorithm:

Input: n = p*q where p, q are distinct odd primes greater than 3

1. Calculate (n+1)/2
2. Calculate k = ((n+1)/2)² mod n
3. Do k = k/2 if k is even
    If k is odd then stop and return k = 3*k + 1 mod n
    While k is not equal to 1

Output: not necessarily a power of (n+1)/2 mod n, in many cases the output is either p, q, or a multiple of p or q.

So I designed an experiment to see which products of primes are affected by this phenomenon up to some small limit, which is easy to calculate by a mobile calculator. For this experiment I take all odd primes greater than 3 and smaller than 41.

5, 7, 11, 13, 17, 19, 23, 29, 31, 37

The following products of primes are affected: 

5*7,5*11,7*11, 5*19, 7*13, 7*19, 7*23, 7*29, 7*31, 11*37

35, 55, 77, 85, 91, 133, 161, 203, 217, 259, 407

(I did this experiment late last night so I might have missed a few.)

When n = 35 then k = 18, k^2 = 9, which is odd so multiply by 3 and add 1 mod 35, 3*9 + 1 = 28 = 3*7

When = 55 then k = 28 k^2 = 14, which is even so divide by 2,  14/2 =  7, which is odd so 3*7 + 1 = 22 = 2*11

And so on.

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 Z_n. 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 Z₃₅ are circled below

Note that 17² mod 35 = 18² mod 35 = 9 mod 35
Also 17⁴ mod 35 = 18⁴ mod 35 = 11 mod 35
and so on for all even powers of 17 and 18 whereas
17³ + 18³ mod 35 = 35
and 17⁵ + 18⁵ 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 Z_n but this might be just wishful thinking to put it mildly.