14.9.16

Trapped In Finite Fields Part 3

In my last few entries I attempted to explain what happens to an integer s after it goes through the algorithm behind the Collatz conjecture and I claimed that it gets trapped in a particular type of a field, which I argued is why it always reaches 1 eventually.

It appears that I stumbled onto an algorithm for finding which finite field s gets trapped into after a number of Collatz iterations.

It all happened while looking at all integers smaller than 100:

All integers s smaller than 100 reach the 5,16,8,4,2,1 path through the Collatz conjecture except for the following three categories of integers:
1. any powers of 2
2. any of 21,42, 84
3. any of 75, 85
The last few powers of 14 mod 27 are 5,16,8,4,2,1 so all integers s < 100 except for integers in the three categories above get trapped in Z27^, more specifically in the 14th row of the exponentiation table of Z27

The first category from the 3 categories above, the one with any power 2^i smaller than 100, always reaches the 2^i, 2^(i-1), ..., 2, 1 path. In other words, it gets trapped in the last few entries of the ((n+1)/2) row of the exponentiation table of Zn where n is any odd integer for reasons explained here.

The second category is composed of integers s < 100 that reach the 21,64,32,16,8,4,2,1 path through the Collatz Conjecture, which are 21, 42, 84. The last few powers are of 54 mod 107 are 21,64,32,16,8,4,2,1 so therefore either one of 21, 42, 84 gets trapped in in Z107^, more specifically in the 54th row of the exponentiation table of Z107

The third category s composed of integers s < 100 that reach the 85,256,128,64,32,16,8,4,2,1 path through the Collatz Conjecture, which are 75 and 85. The last few powers are of 214 mod 42are 85,256,128,64,32,16,8,4,2,1 so therefore both 75 and 85 get trapped in in Z427^, more specifically in the 214th row of the exponentiation table of Z427

Below are few tools including a tool for finding all powers of (n+1)/2 mod n for an odd n and a tool for listing all integers in the Collatz trajectory for a given integer.

While doing this fun exercise I came across a remarkable claim, which I don't have the vocabulary to state yet so I'll state it in an algorithmic form.

Algorithm for finding which finite field n an integer s gets trapped into during Collatz iterations:
//expects an input of the largest power of 2 in the path through the Collatz Conjecture and the first integer to reach the path

1. Let k be the largest power of 2 in the path, let u = k - 1 and let n = k + 1.
2. Let m be the first integer to reach the path, then u = u - m
3. Compute n  =  u + n