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.