Saturday, August 27, 2016

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.

Friday, August 19, 2016

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

Sunday, August 14, 2016

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.

Friday, August 12, 2016

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.

Tuesday, August 9, 2016

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 Zn. 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 Z35 are circled below

Note that 172 mod 35 = 182 mod 35 = 9 mod 35
Also 174 mod 35 = 184 mod 35 = 11 mod 35
and so on for all even powers of 17 and 18 whereas
173 + 183 mod 35 = 35
and 175 + 185 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 Zbut this might be just wishful thinking to put it mildly.

Saturday, July 30, 2016

Generating multiples of k mod n

In my previous post I showed how one row of the multiplication table of Zn when n is the product of distinct odd primes can be generated using less iterations than others. 

My function for generating multiples of an arbitrary k will always make n-1 iterations to get to the n-k element, which is the last element in the kth  row of the multiplication table of Zn 


However, as I showed in my previous post, if k = (n+1)/2 then the kth  row of the multiplication table of Zn  has the following pattern [k, 1, k+1, 2, k+2, 3, k+3,..., n-1, n-k],
which can be produced in half the number of iterations needed in an additive function for an arbitrary k which takes n-1 iterations.

Also ((n+1)/2)*2 = n+1 = 1 mod n because n = 0 mod n and 2 = ((n+1/2))r-1 where r is the order of (n+1)/2

Similarly, 
((n+1/2))2 * 22 = 1 mod n and 22 = ((n+1/2))r-2 mod n 
((n+1/2))3 * 23= 1 mod n  and 2=((n+1/2))r-3
((n+1/2))4 * 2= 1 mod n and 24 = ((n+1/2))r-4 mod n 
.
.
.
and so on until a lonely square is reached.

In general I claim that:


Claim: If n is the product of distinct primes and k and r are integers such that kr= k mod n and r is the smallest such integer then for all i such that 1< i < r 

ki * kr-1-i = 1 mod n        | if GCD(k,n) = 1
ki * kr-i = k mod n           | if GCD(k,n) > 1

When k = (n+1)/2, every second integer in the kth  row of the multiplication table of Zn (in other words the array of multiples of k) is just the index of the previous integer starting from an initial k, which is then gradually increased by 1, forming the following sequence [k, 1, k+1, 2, k+2, 3, k+3,..., n-1, n-k]



When k = ((n+1)/2)2 mod n, every fourth integer in the array of multiples of k is the index of the block of the previous 3 integers starting from k, k+k, k+k+k, which are then gradually increased by 1, forming the following sequence [k,  k+k,  k+k+k, 1,  k+1, k+k+1, k+k+k+1, 2,..., n-1, n-k]

With this in mind and the observations I made here, if k = ((n+1)/2)2 mod n then all multiples of k can be generated in 1/4 of the number of iterations needed for an arbitrary k although the total number of  inserts into the array of multiples remains the same.

I just need to initialize the first 3 values and calculate the actual number of iterations, which is the floor of (n-1)/4, and then iterate n/4 times while inserting 4 values into the array at each iteration because apparently I'm not satisfied with just inserting only 2   values at the same time.

Similarly, if k = ((n+1)/2)3 mod n then all multiples of k can be generated in 1/8 of the number of iterations needed for an arbitrary k and so on although the total number of inserts into the array of multiples remains the same.


Here's the implementation for k = ((n+1)/2)2 mod n:

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all multiples of ((n+1)/2)^2 mod n 
 ---------------------------------------------------- */ 

function generate_multiples(n)
{ 
 var k_one = (((n-1)/2)*((n-1)/2))%n;
 var k_two = (k_one+k_one)%n;
 var k_thre = (k_two+k_one)%n;
 var end = Math.floor(n/4);
 var perm = new Array();
 perm.push(0);perm.push(k_one);
 perm.push(k_two);perm.push(k_thre);
 
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     k_one = k_one+1;
     perm.push(k_one);
     k_two = k_two+1;
     perm.push(k_two);
     k_thre = k_thre+1;
     perm.push(k_thre);
 }  
 return perm; 
} 
 

This array of multiples may end up with up to 3 additional values but this will not affect the generic function for generating powers of k mod n that simply permutes through the array of multiples of k mod n.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all multiples of ((n+1)/2)^2 mod n
and use that array to generate all powers of
 ((n+1)/2)^2 mod n, which are all powers of 4 mod n 
in reverse order
 ---------------------------------------------------- */ 

function generate_multiples(n)
{ 
 var k_one = (((n-1)/2)*((n-1)/2))%n;
 var k_two = (k_one+k_one)%n;
 var k_thre = (k_two+k_one)%n;
 var end = Math.floor(n/4);
 var perm = new Array();
 perm.push(0);perm.push(k_one);
 perm.push(k_two);perm.push(k_thre);
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     k_one = k_one+1;
     perm.push(k_one);
     k_two = k_two+1;
     perm.push(k_two);
     k_thre = k_thre+1;
     perm.push(k_thre);
 }  
 return perm; 
} 

function generate_powers(n)
{
 var index = 0;
 var perm_slot =1;
 var perm = new Array(); var powers = new Array();
 perm = generate_multiples(n);
 do{
    index = perm_slot;
    perm_slot = perm[index];
//the order of k mod n can also be found 
//through counting the # of iterations
    powers.push(perm_slot); 
   }while(perm_slot != 1)
 return powers;
}




Thursday, July 14, 2016

Generating Powers of 2 Faster

In a previous post I described an algorithm for generating powers of 2 mod n when n is an odd integer.

It required the generation of an array of multiples of 2 mod n that relied on consecutively adding 2 to an initial integer while checking to see if the new integer exceeds n and resetting the process thus making n iterations on an input of n and then some. This function generated the row at 2 of the multiplication table of Zn, which I then used to generate the row at 2 of the exponentiation table of Zn.

Today I propose a new function that makes only (n-1)/2 iterations on an input of n based on the observation that the row at (n+1)/2 of the exponentiation table of Zn is equivalent to the row at 2 of the exponentiation table of Zin reverse order.


In this case it is sufficient to generate the row at (n+1)/2  of the multiplication table  of Zn, which can be generated faster based on the following claim:

Claim: Every odd element of the row at (n+1)/2  of the multiplication table of Zn,is equal to the sum of the previous element and 1 starting from (n+1)/2 and every even element is also equal to the sum of the previous element and 1 starting from 1 up to (n-1)/2.

This means that at each iteration two elements of the multiplication table of Zcan be added to the array of multiples as opposed to just one and neither will exceed n by construction, therefore there's no need to add an extra check.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all powers of 2 and (n+1)/2 mod n 
 ---------------------------------------------------- */  
//generate powers of 2 from highest to lowest exponent
function powers_of_two_backwards(n)
{
 var index = 0;
 var perm_slot =1;
 
 var perm = new Array(); var powers = new Array();
 perm = generate_faster_permutation(n);
 do{
    index = perm_slot;
    perm_slot = perm[index];
    powers.push(perm_slot); 
   }while(perm_slot != 1)
 return powers;
}
//generate row at (n+1)/2  of the multiplication table 
function generate_faster_permutation(n)
{ 
 var start = (n+1)/2;
 var end = (n-1)/2;
 var perm = new Array();
 perm.push(0);perm.push(start);
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     start = start+1;
     perm.push(start);
 }
 perm.pop();  
 return perm; 
}


Here's a point and click implementation of the algorithm above.




Note: this algorithm can also be used to find the order of 2 mod n if instead of adding elements to a data structure powers_of_two_backwards(n) counts the number of iterations it makes since the number of iterations in this cycle is precisely the order of 2 and (n+1)/2 mod n.

Everybody Uses Abstract Algebra Every Day

Although it is a new branch of Mathematics, Abstract Algebra has far reaching applications in other scientific fields like Computing Science and Physics.

Actually, everyone uses pure Abstract Algebra on a daily basis. In a few paragraphs I will show how but first here's how this new branch relates to the old branch of Elementary Algebra, which is the algebra most people learn first.

One of the fundamental algorithms of Abstract Algebra is an algorithm from Elementary Algebra called the Division algorithm, which states that when one non zero integer divides another integer, the dividend is equal to the divisor times a unique quotient plus a unique remainder.

In other words, any 2 integers a, b where b > 0 can be expressed as a = bq + r where q and r are unique integers such that 0 <= r < b where r is the remainder when a is divided by b.

For example, let a = 12 and b = 12 then r = 0 since 12 = 12*1 + 0

This is the same as saying  that 12 is congruent to 0 modulo 12 because 12 - 0 is divisible by 12.

Or in other words, 12 = 0 in the set of all integers from 0 to 11. 

It can be verified that the sum s of any two integers from the set of all integers from 0 to 11 is still in that set if it is calculated as s = 12q + r 

For example, let s = 9 + 5 = 14. While 14 is not in the set from 0 to 11, 14 can be uniquely represented as 14 = 12*1 + 2 so 14 = 2 modulo 12 

The fact that the sum of any two elements can be represented by another element in that set means that the set is closed with respect to the operation of addition, and that coupled with a few other properties is what makes this set a group under the operation of addition, it is also a ring under this and the operation of multiplication, and a blank canvas under the operation of exponentiation.

This set is called Z12 since it is the first positive 12 integers of Z and Z is the set of all integers.

Now let’s get back to how everyone uses this on a daily basis. Enter the clock. Everyone uses the clock except for a few lucky people who don’t care about concrete measurements of time. 

At some point of each day most people need to calculate how many hours are left of something, how many hours until something happens and so on. In doing so they are dealing with Abstract Algebra, or more specifically, with the abstract structure of Z12 under addition.


The table on the left of the graphic above illustrates the addition table of Z12
Note that each row in that table is shifted by 1, which makes it easy to visualize.

Since it is 9 o'clock in City A and City A is 5 hours ahead of City B then it is currently 14 o'clock in City B and since 14 = 12*1 + 2 so 14 = 2 modulo 12 then the clock in City B shows 2.


Further reading:
Algebra by Thomas W. Hungerford
The Theory of Algebraic Number Fields by David Hilbert
Applied Abstract Algebra by Lidl & Pilz
Integers, Polynomials, and Rings by Ronald S. Irving

Tuesday, July 5, 2016

Recurring Oddities

I already provided a brute force algorithm for finding the smallest square root of ((n+1)/2)^2 mod n where n is the product of distinct primes. That algorithm simply multiplies progressively larger integers and takes the remainder after dividing n.

I came across a recurrence relation, which can be used to generate squares of consecutive integers  modulo n and it is based on the following observation: each subsequent square term is equal to the previous square term plus an odd integer, which is calculated using the index of the previous term.

Consider the sequence formed by squaring integers consecutively:

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

Conjecture: If a2 = 4 then ai = ai-1 + (2*(i-1) + 1) where i > 2

This conjecture seems to hold for finite fields as well so it can be easily implemented.

While I still consider it a brute force function, it is a tad more elegant brute forcing than multiplying and dividing to find the remainder. The previous Javascript function used the remainder operator because Javascript doesn't have a modulo operator yet.

Note that by using the recurrence relation above I eliminate the need to use the modulo or remainder operator since there are no large multiplications because the skewy is an integer smaller than (n+1)/2 by definition.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find x such that x the smallest square root of
 ((n+1)/2)^2 mod n called the skewy mod n
 ---------------------------------------------------- */  
//n must be the product of 2 distinct primes, k is ((n+1)/2)^2 mod n
function find_square_root_slowly_recurrence(n, k)
{
 var index = 2;
 var sq_rt = 4;
 while(sq_rt != k)
 { 
  sq_rt = sq_rt + (2*index + 1);
  index = index+1;
  if(sq_rt > n){sq_rt = sq_rt - n;}  
 }
 return index;
}



Tuesday, June 28, 2016

The Skewy

A few months ago I had a deeply profound conversation regarding the merits of the word "skewier".

Apparently, my blog is one of the very few places on the Interwebs where this word is being used. I used "skewier" while talking about text-based CAPTCHAs.

Unfortunately, there's no entry on "skewy" or its comparative "skewier" in any dictionaries so I decided to make my own entry here to explain how "skewy" is different than skewed and why it deserves a special place in modern dictionaries.

Furthermore, I decided to give it a second meaning in the context of Mathematics because I'm fairly convinced that Mathematics is not as appealing as it could be as a direct result of not having enough definitions for people to memorize. Just open any Mathematics textbook and see what I mean.



Also I came up with this definition because I'm too lazy to say "the smallest square root of blah blah" and because I want the glossary section of this blog to look meatier.

Hopefully people around the world will recognize the merits of this word someday and allow it to be used in Scrabble games.

But for now, I'll just make another strange claim, which follows from Corollary 1 from this post

Claim: If s is the skewy mod n then 2s2 = ((n-1)/2) + 1