15.9.16

Collatz Exit

Definition: An exit point in relation to the Collatz conjecture is the last odd integer reached before reaching a power of 2.

Example: Let s = 10 then the Collatz exit point is 5 since 10/2 = 5 and 3*5 + 1 = 16, which is a power of 2.

The first few Collatz exit points are 5,21,85,341,1365,2731,5461,21845,87381

The sequence of Collatz exit points does not exist in the OEIS database.

Claim: If 2r - 1 is divisible by 3, then (2r - 1)/3 is a Collatz exit point.

Proof: A Collatz exit point is an odd integer x such that 3x + 1 is equal to a power of 2.
Let k = 2r - 1. Since k is divisible by 3 then k/3 is an integer i = k/3 therefore 3i = k and since k = 2r - 1 then 3i = 2r - 1 so 3i + 1 = 2r  .'.

Conjecture: If r is an even integer greater than 2, then 2r - 1 is divisible by 3

Definition: An exit path in relation to the Collatz conjecture is the last few integers reached in a Collatz trajectory starting from the Collatz exit point.

Example: Let s  = 10 then its Collatz exit path is 5,16,8,4,2,1

Note: In my previous blog entry I used the term "Collatz path" but I decided that "Collatz exit path" is a more descriptive term.

Definition: A Collatz trap is an odd integer n such that the last few powers of (n+1)/2 correspond to a Collatz exit path.

Example: Let n = 27, the last few powers of 14 mod 27 are 5, 16, 8, 4, 2, 1, which correspond to the Collatz exit path of 10.

The first few Collatz traps are: 27, 107, 427, 1707, 6827, 27307, 109227, 436907.

It appears that the sequence of Collatz traps already exists in the OEIS database but not in connection with the Collatz conjecture. I find this fascinating.

With these definitions in mind, I refine my previous algorithm for finding a Collatz trap from a Collatz exit path as follows:

Claim: Given a Collatz exit path [m, 2r, 2r-1, 2r-2, ... , 1] then a Collatz trap n is equal to:

n = (2r + 1) + ((2r - 1) - m)

Claim: Given a Collatz exit point m, then a Collatz trap is equal to 5*m + 2

Claim: For each unique Collatz exit point m, there exists a unique Collatz trap.

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

13.9.16

Trapped In Finite Fields Part 2

In my previous entry I attempted to show why the Collatz Conjecture is true for any integer s by suggesting that s gets trapped in a finite field for a lack of a better phrase to describe this process.

In particular, I imagine it gets trapped into a portion of the ((n+1)/2)th row of the exponentiation table of Zn where n is some odd integer.  

The ((n+1)/2)th row of the exponentiation table of Zn, where n is some odd integer, is the 2nd row of the exponentiation table of Zn in reverse order, which means that the last few elements of it are consecutive powers of 2 in descending order. Furthermore, dividing any even element in this row by 2 produces the next element in the row and there are elements k,l in that row not necessarily distinct such that 3*k+1 = (l*((n+1)/2) mod n).

Most of this I haven't proven yet. So here are a few examples to (hopefully) better illustrate what I mean:

Example: Let n = 35. It can be verified that row 18 is equivalent to row 2 in reverse order, and so it ends in consecutive powers of 2 in descending order. Furthermore, dividing any even element in this row by 2 produces the next element in the row and there are elements k = 22, l = 29 in that row not necessarily distinct such that 3*22+1 (mod 35) = 29*18 (mod 35)




It may sound a bit counterintuitive that n is an odd integer because if n is even then it is divisible by 2 and so it would seem that it would fall right into the algorithm behind the Collatz conjecture.

However, this does not appear to be the case. I conjecture this to be the key to solving this problem.

Example: the exponentiation tables for n = 6 and n = 10 are given below:

Neither the (n/2)th nor the ((n/2)+1)th row ever reach consecutive powers of 2. In both of these cases n is a product of 2 and an odd integer, and in both cases  (n/2)i = (n/2) mod n and ((n/2)+1)i = ((n/2)+1) mod n for all i < n.

In general I claim the following:

Claim: If n is an even integer then for all i such that 1 < i < n
(n/2)i = (n/2) mod n if n  = 2m for some odd integer m
(n/2)i = 0 mod n  if n  = 2rm for some odd integer m and some integer r

Claim: If n is an even then for all i such that 0 < i < n
(n/2)i * 2i = 0 mod n 

In contrast:

Claim: If n is an odd integer and r is the order of 2 mod n then for all i such that 1 < i < r
((n+1)/2)i * 2i = 1 mod n

Below I attach a tool for finding all powers of k mod n for any integer n.