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.


6.9.16

Trapped In Finite Fields

I think I know why the algorithm behind the Collatz conjecture always reaches 1 instead of reaching some infinite cycle for all examples tried so far and I think that it will always reach 1 first.

I think the Collatz Conjecture is bridging the gap between continuous and discrete Mathematics.

Unfortunately, what I think is irrelevant if I can't state it correctly or prove it. I will attempt to do so because I'm stubborn. I already attempted to do so in my first entry on the Collatz conjecture but looking at it now it looks like a lot of rambling. So I give it another, hopefully less rambly, try.

Any integer s is either even or odd. If is even, then it will be divided by 2 by the Collatz algorithm until it becomes odd and then it will peak as it gets multiplied by 3 and added to 1 and so on.

I conjecture that at some point during the peaking, the resulting odd integer, which I will call k, is such that 3*k+1 = (k*((n+1)/2) mod n) for some odd integer n.

At this point the trajectory of s under the Collatz map collides with or it gets trapped into a portion of the ((n+1)/2)th row of the exponentiation table mod n starting at 3*k+1.

The ((n+1)/2)th row of the exponentiation table modulo n for some odd integer n is the 2nd row of that same exponentiation table in reverse order.

In other words, the set of all consecutive powers of ((n+1)/2) mod n is the set of all consecutive powers of 2 in reverse order.

This means that the cardinality of the two sets is equal, and it is equal to the order of 2 mod n. Furthermore, the last few elements of the set of all consecutive powers of ((n+1)/2) mod n are powers of 2 mod n

If an element r of the set of all consecutive powers of ((n+1)/2) mod n is even then the next element in the set is r/2.

So if r is even, some x trajectory under the Collatz map will overlap with the portion of the set of all consecutive powers of ((n+1)/2) mod n  starting at r and if k is the first odd integer on this trajectory such that 3*k+1 = (k*((n+1)/2) mod n) then the two trajectories become identical starting at r, and they reach a stopping point 1 after hitting powers of 2.

The reason why it will always reach this particular stopping point is because even if s starts out as a multiple of 2 (which is the only time when the ((n+1)/2)th row of the exponentiation table modulo n will reach an infinite cycle as opposed to powers of 2), s will be divided by 2 by the Collatz algorithm until it reaches an odd integer, which exposes the trajectory for a lack of a better way to describe this.

4.9.16

A Couple Of Sequences

Two integer sequences that I recently submitted to the OEIS have been approved. The first sequence is the sequence of Collatz primes(A276260) , which I talked about here.



http://oeis.org/A276260


The mesmerizing thing about this sequence is the fact that there are only 9 known terms of it so far, and if a 10th term exists, it must be greater than 10^9.

The other sequence that I submitted was the one I talked about here, which is now sequence A276290 in OEIS.

The interesting thing to me is the fact that so far no counter example has been found to my conjecture that if n is the product of two odd primes p and q and p = 3 then neither p nor q is in the trajectory of n+1 under the Collatz 3x+1 map.

This makes me wonder if there are primes other than 3 for which this conjecture also appears to be true.

A Square of A Square

In my Recurring Oddities entry I talked about a recurrence relation where each subsequent term was equal to the previous term plus an odd integer, which I calculated using the index of the previous term and I claimed that this recurrence relation generates the sequence formed by squaring integers consecutively:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225,... [A000290]

9 = 4 + (2*(3-1) + 1)
16 = 9 + (2*(4-1) + 1)
25 = 16 + (2*(5-1) + 1)
.
.
.

Claim: If a2 = 4 then ai = ai-1 + (2*(i-1) + 1) where i > 2 generates the sequence formed by squaring integers consecutively.

Proof: Although I never proved this when I first made this claim, the proof of this is very simple and it involves basic algebra.

Since ai = n2 , ai-1 = (n-1)2 , and (i-1) = (n-1), the ai = ai-1 + (2*(i-1) + 1) recurrence relation becomes:
n2 = (n-1)2 + (2*(n-1) + 1)
     = (n2 - 2*n + 1) + (2*n - 2 + 1)
     = n2 - 2*n + 2*n - 2 + 2
     = n
     .'.

I used this recurrence relation to find the smallest square root of ((n+1)/2)2 mod n, which I then used to find lonely squares, or integers k such that k2 = 1 mod n where n is the product of distinct primes because I claimed a lonely square is just 2 times the smallest square root of ((n+1)/2)2 mod n.



There are also another type of interesting integers, which I endearingly call foursome squares.

Definition: Foursome squares are integers k such that  k2 = 4 mod n

Example: Let n = 35, then k = 23 since 232 = 4 mod 35 but also 122 = 4 mod 35 and also 22 = 4 mod 35 and 332 = 4 mod 35

Claim: If k is a foursome square then k*((n+1)/2) mod n is a lonely square.

27.8.16

Collatz Factoring

Definition: A Collatz product is the product n of 2 odd primes p and q such that n+1 reaches p or q when put through the algorithm behind the Collatz conjecture.

As I already mentioned here, such products seem to appear much more frequently than single such primes, or primes that I called Collatz primes.

For example, from all products of p = 3,5,7,11,13,17 times all other primes q = from p to 53, the following are Collatz products:

p=3 for all q from 3 to 53: [0] (see conjecture at the bottom of this page)

p=5 for all q from 5 to 53: [25, 35, 55, 65, 85, 95, 115, 145, 155, 185, 205, 215, 235, 265]

p=7 for all q from 7 to 53: [ 77, 133, 161, 203, 217, 259, 287, 329, 371 ]

p=11 for all q from 11 to 53: [143, 209, 253, 341, 407, 473, 517, 583 ]

p=13 for all q from 13 to 53: [403, 481, 611, 689]

p=17 for all q from 17 to 53: [391, 493, 527, 629, 697, 799, 901

And so on. 

The following sequence emerges:

25,35,55,65,77,85,95,115,133,143,145,155,161,185,203,205,209,...


Below is an algorithm for generating all products of p given an array of odd primes.

/* -------------------------------------------------
 This content is released under the GNU License
 http://www.gnu.org/copyleft/gpl.html
 Author: Marina Ibrishimova
 Version: 1.0
 Purpose: Find Collatz Products
 ---------------------------------------------------- */
//takes an array of odd primes and a single prime cur
function genrate(primez, cur)
{
var factorable = new Array();
for(i=0; i<primez.length; i++)
{
 if(isitCollatzProduct(cur,primez[i])!=0)
 {
  factorable.push(cur*primez[i]);
 }
}
return factorable;
}
function isitCollatzProduct(p,q)
{
var n = p*q;
var cur = n+1;
while(cur != p && cur != q && cur != 2)
{
if(cur%2!=0)
{
cur = 3*cur + 1;
}else
{cur = cur/2;}
}
if(cur === p || cur === q ){return cur;}
else {return 0;}
}

Conjecture: If n is the product of two odd primes p and q and p = 3 then n is not a Collatz product.

19.8.16

Collatz Primes

Although I found a counter example to the last claim from my previous Collatz adventure, which means that it is false in general, I decided to look for which products of primes it is true. It turns out that from all products of primes for primes from 5 to 37 this claim is true for almost all products.

In other words, almost all of these products of primes are reduced to either one of the primes of which they are composed, or is a multiple thereof when ((n+1)/2 is subjected to the algorithm behind the Collatz Conjecture. 

Obviously I found this fascinating but not particularly clean or elegant. So I decided to look what happens to individual odd primes p when (p+1)/2 is subjected to the same algorithm.

Definition: A Collatz prime (or a selfie prime) is an odd prime p such that p+1 reaches p when put through the algorithm behind the Collatz conjecture.

The first few such primes are:

5, 13, 17, 53, 61, 107, 251


Note: This sequence is currently not in the encyclopedia of integer sequences.

Observation:  It appears that not all products of Collatz primes are reducible to the primes of which they are composed and yet many products of primes that are not Collatz primes can still be reduced to the primes of which they are composed

Observation 2: The distribution of these primes is strange, and I haven't yet been able to find another Collatz prime after 251 

Below is a simple algorithm to check if an odd prime is a Collatz prime

14.8.16

Powers of Collatz Part 3

In my previous article I showed what happens to some products of distinct odd primes p*q = n when the algorithm behind the Collatz conjecture is applied to ((n-1)/2)^2 mod n.

I did this by stopping the first time an odd integer k is encountered and returning (3k+1) mod n

Algorthm PartialCollatz
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)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

In many cases, the output was a multiple of one of p or q. At first those cases look random and it is possible that's all they are but it is also equally likely that there exists some elusive pattern. 

Like for example, when looking at all of the products of all primes up to 37, it appears that all primes except for 3 and 17 are affected and could potentially produce the desired output when multiplied by another prime, and yet not all products of primes up to 37 were affected.

affected primes = 5, 7, 11, 13, 19, 23, 29, 31, 37

affected products = 5*7,5*11,7*11, 5*19, 7*13, 7*19, 7*23, 7*29, 7*31, 11*37 

I thought about it and I decided to group certain products of primes based on which prime the output was a multiple of and I came up with a new confusing notation to get back at all confusing notations I've encountered.

5*7  => 7 ( 7*13 => 7, 7*23 => 7, 7*29 => 7, 7*31 => 7)
5*11 => 11 (7*11 => 11, 37*11 => 11)
5*19 => 5

And then I decided to check what happens to 19 further down the line
7*19 => 19  (19*53 => 19, 19*71 => 19, 19*149 => 19)

And then I decided to see what happens to 5 further down the line when I encountered something that is probably known already.

Claim: If n+1 is equal to a power of 2 then k = (n+1)/2 is also a power of 2 and the algorithm behind the Collatz conjecture when applied to k doesn't reach any other odd integer or non-power of 2 before it reaches 1.

This is just a trivial claim that I find curious nevertheless.

But I stumbled onto something potentially bigger after asking myself the following question:

If the initial output is not a multiple of p or q then what happens if I keep applying the Collatz algorithm unrestricted by mod n?

Claim: If I keep applying the Collatz algorithm unrestricted by mod n to the output of the PartialCollatz algorithm then I will eventually reach a power of 2 but immediately before I do, I will reach p or q or a multiple of p or q.

Or so it seems for the few examples I've tried.

Update: This claim is false. Counter example: 7*43 although it did take me quite a few tries to get to it.

12.8.16

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)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)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.