31.12.16

2016 Sequences

I came up with 7 different sequences in 2016 and I thought I'd put them all in one place as some of them are slightly related to one another.

1. The first sequence is the sequence generated by powers of 2 mod n when n is the product of 2 distinct safe primes. The sequence was published in the OEIS.org with sequence number is A269453. Here are the first few terms of the sequence:

12, 20, 30, 44, 33, 92, 110, 116, 69, 174, 164, 230, 212, 246, 290, 318, 332, 356, 410, 253, 452, 249, 530, 534, 524, 638, 678, 692, 716, 830, 393, 902, 764, 890, 932, 956, 1038, 1166, 1130, 537, 1004, 573, 1334, 1124, 1310, 1172, 1398, 717, 753, 1436, 1730, 913, 1886, 1686, 1790

2. Then came the the sequence of the products of two distinct safe primes, which is now published in the OEIS.org under sequence number A269452

24, 40, 60, 88, 132, 184, 220, 232, 276, 348, 328, 460, 424, 492, 580, 636, 664, 712, 820, 1012, 904, 996, 1060, 1068, 1048, 1276, 1356, 1384, 1432, 1660, 1572, 1804, 1528, 1780, 1864, 1912, 2076, 2332, 2260, 2148, 2008, 2292, 2668, 2248, 2620, 2344, 2796, 2868, 3012, 2872, 3460, 3652, 3772, 3372


3. Looking at these 2 sequences made me discover a third sequence, which I dedicated to my great grandmother Yona because at the time I thought it was the most important result I'd come up with. This sequence consists of safe primes not congruent to -1 mod 8 and it is now published with a sequence number A269454.

5, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, 1523, 1619, 1907, 2027, 2099, 2459, 2579, 2819, 2963, 3203, 3467, 3779, 3803, 3947, 4139, 4259, 4283, 4547, 4787, 5099, 5387, 5483, 5507, 5939, 6659, 6779, 6827, 6899, 7187, 7523


The next 3 sequences I came up with involve the Collatz conjecture, which is an open problem in Mathematics. 2 of these sequence were published and the last one was denied and so it remains unpublished because it seemed "artificial"

4. The first sequence of the Collatz trio is the sequence of Collatz primes(A276260), and it only has 9 terms. If a 10th term exists, it would have to be really really large.

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

5. The second sequence is the sequence of Collatz products, and it has many more terms. It is published under the sequence number A276290 .

25, 35, 55, 65, 77, 85, 95, 115, 133, 143, 145, 155, 161, 185, 203, 205, 209, 215, 217, 235, 253, 259, 265, 287, 295, 305, 329, 341, 355, 365, 371, 391, 395, 403, 407, 415, 427, 437, 445


6. The third sequence of the Collatz trio was never published and here I explain it in some detail.  The first few terms are:

5,27,21,107,85,427,341,1707,1365,6827, 5461

7. The last sequence that I came up with in 2016 is the sequence I described here. I haven't attempted to publish this sequence anywhere yet. The first few terms are:

15, 21, 51, 93, 195, 381, 771, 1533, 3075, 6141

2016 has been the year of discovery for me. I discovered many different results, some of which I even managed to prove. Also in 2016 I learned not to be intimidated by sharing my results with the public.

30.12.16

Just another sequence

In my previous post I talked about the order of 2 mod n where n is an integer such that either n = 2^i + (2^(i-1) - 3) when i is even or n = 2^i + (2^(i-1) + 3) when i is odd.

I conjectured that the order of 2 mod n for such n is i + (i - 2) regardless of whether i is even or odd.

The recurrence relation for generating all such n up to a limit is :

2i + (2(i-1) - 3) if i is even
or 2i + (2i-1 + 3) if i is odd

For the fun of it, I wrote a simple script to generate the first few such integers up to some limit.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate the 3sequence  
  
 ---------------------------------------------------- */  
function gen_seq(i, limit, a)
{
 var j = i - 1;
 var n = Math.pow(2,j);
 var m = Math.pow(2,i);
 if (i < limit)
 {
  if (i % 2 != 0)
  {
   n = n + 3;
  }
  else
  {
   n = n - 3;
  }
  a.push(m+n);
  i = i + 1;
  gen_seq(i, limit, a)  
 }
 return a;
}

Here's the output for limit = 12:

15, 21, 51, 93, 195, 381, 771, 1533, 3075, 6141

Obviously, there is another way to generate this sequence than the one I use in my script. Each term in the sequence can also be generated by multiplying 3 and 2^i - 1 if i is odd or 3 and 2^i + 1 if i is even.

3*5 = 15 where 5 = 2^2 + 1
3*7 = 21 where 7 = 2^3 - 1
3*17 = 51 where 17 = 2^4 + 1
3*31 = 93 where 31 = 2^5 - 1

and so on.

28.12.16

Between 2 i's

Previously I talked about the order of 2 mod n when n is either equal to 2^i + 1 or 2^i - 1

How about the order of 2 mod n for other integers n, which are between 2^i and 2^(i+1)?

21.12.16

The circle of i

Every day many people around the world look for the next largest Mersenne prime. A Mersenne prime is a Mersenne number that's also prime.

A Mersenne number is an integer of the form 2^i - 1 where i must also be prime but this condition is not strongly enforced in all texts and certainly not on this blog.

I prefer the loose definition where i is not necessarily a prime. With this loose definition in mind, the first few Mersenne numbers are:

0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, ...

The first few Mersenne prime numbers are:

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ...

In a previous post I proved that the order of 2 mod n is equal to i where n is a Mersenne number of the form 2^i - 1

For example, the order of 2 mod 15 is 4 and 15 = 2^4 - 1.

A Mersenne number can also be a product of 2 or more distinct primes.

The first few products of 2 distinct primes that create a Mersenne number are:

5*3 = 15, 7*73 = 511, 23*89 = 2047, 47*178481 = 8388607


At the other end of the spectrum of Mersenne numbers are integers of the form 2^i + 1.

They don't have a fancy name but some of them do show up in fancy parts of Number Theory. I'll call them MersenneSofit numbers.

The first few such numbers are:

2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, ...

The only prime MersenneSofit numbers that I was able to find are also Fermat primes even though the set of MersenneSofit numbers is not equivalent to the set of Fermat numbers. I find this quite fascinating although it is possible I missed a prime in my savage late night calculations.

Here are the only MersenneSofit primes I could find so far:

3, 5, 17, 257, 65537

As I already said, these are also the only Fermat primes currently known.

Regardless of whether prime or composite, I claim that the order of 2 mod n for all n of the form 2^i + 1 is 2*i.

A Mersenne Sofit number can also be a product of distinct primes. The first few products of 2 distinct primes are:

5*13 = 65
3*43 = 129
17*241 = 4097
3*2731 = 8193
3*43691 = 131073
3*174763 = 524289
17*61681 = 1048577
3*2796203 = 8388607
17*15790321 = 268435457

Note: although there are more Mersenne primes than MersenneSofit primes, there seem to be less products of 2 distinct primes that form Mersenne numbers than there are products of 2 distinct primes that form MersenneSofit numbers.

7.11.16

The order of 2 mod n when n is a Mersenne number

In my previous entries I discussed the largest power i of 2 such that 2i <  n for any odd integer n and I claimed a few things about it. Here I make another claim related to Mersenne numbers that I managed to prove.

Claim: If n = 2i - 1 (also known as a Mersenne number), then the order of 2 mod n is i.

Proof: If n is a Mersenne number then by definition n = 2i - 1 so then n - 1  = 2i and so clearly 2i = 1 modulo n.

By definition, the order of an element a modulo n is the smallest integer b such that ab = 1 mod n so it remains to show that i is the smallest integer such that 2i = 1 modulo n.

I'll show this by contradiction. Suppose there exists an integer k such that k < i and yet 2k= 1 mod n. Transforming this congruence relation to a diophantine equation yields

If 2= 1 mod n then for some integer x,  nx + (-1) =  2k  so nx - 1  =  2k

Clearly, x must be greater than 1 since it is given that n - 1 = n*1 - 1 = 2i and k is not equal to i

Therefore, (nx - 1) > (n - 1) so therefore 2k > 2i so therefore k > i, which is a contradiction to the supposition that k < i ...

Example: It is easy to calculate the order of two mod n for the first few Mersenne numbers.
The first few Mersenne numbers are 3, 7, 15, 31, 63, 127, 255 and the order of 2 mod n for each of these choices is 2,3,4,5,6,7,8 respectively.


Below is a slow calculator for finding the order of 2 mod n for any odd integer n:


14.10.16

A Simple Formula For Finding The Order Of An Element

I have shown quite a few ways for finding the order of an element but all of the methods listed here so far entail going through a bunch of iterations. None of these methods are that exciting to me, not even the ultra sleek way of generating powers of 2 mod n backwards.

For the past several years I have been chasing after a far grander idea, the idea that there is a simple formula for finding the order of 2 mod n. It seems like there is a quick formula indeed but it is not the same for all.


Claim: If n is an odd integer such that n = 2i + 1 then the order of 2 mod n is 2*i.


Furthermore, given the set of all powers of 2 smaller than n, say S1 = [2, 4, 8,  ..., 2i] then the set of the remaining powers of 2 mod n, is S2 = [2i - 1, 2i - 3, 2i - 7, ..., 1]


Proof: Later


Example: Let n = 33. Clearly 33 = 2+ 1 so the order of 2 mod n is 2*5 = 10. It can be verified that 210 = 1 mod 33



Note: 2i + 1 can be either a prime or a composite integer but the formula stays the same. For all other n it seems that there are two different formulas depending on whether n is a prime or a composite.



Interestingly enough, if I construct a set of powers of 2 plus 1,  namely the set of 2i + 1 for i = 1,2,3 4, 5, 6... then obviously this set is [3, 5, 9, 17, 33, 65, …]

Note that the order of 2 mod 3 is 2, the order of 2 mod 5 is 4, the order of 2 mod 9 is 6, the order of 2 mod 17 is 8, the order of 2 mod 33 is 10, the order of 2 mod 65 is 12, and so on.

Reminder: the order of 2 mod n is the smallest integer k such that 2k = 1 mod n


Below is a slow calculator for finding the order of 2 mod n for any odd integer n:




So I boldly claim what no one (hopefully) has claimed before:


Claim: The set of the order of 2 mod n for each element of the set [3, 5, 9, 17, 33, 65,…]
is precisely the set of all even integers [2, 4, 6, 8, 10, 12, …]


2.10.16

Collatz Exit Sequence Explained

As I already mentioned earlier tonight, a sequence I submitted to the OEIS on the 16th of September, 2016, a day after I wrote the following entry, has been rejected because it allegedly 'is very artificial". 




The first few terms of this sequence are 5,27,21,107,85,427,341,1707,1365,6827, 5461

Here I present the recurrence relation, or formula, which I use to generate it.


a1 = 5 


For i > 1, then:

ai = 5ai-1 + 2 if i is even
ai = ai-1 - (ai-2 + 1) if i is odd


Here's a simple program to generate the first i terms of the sequence in Javascript:

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate the sequence of Collatz exits and 
 Collatz traps
 ---------------------------------------------------- */  
 function generate_cet(n)
{ 
 var a = new Array();
 a.push(1);a.push(5);
 
   for(i=2; i<=n; i++)
 {
     if(i%2 == 0){
      a.push(5*(a[i-1]) + 2);    
     }
     else{
      a.push(a[i-1] - (a[i-2] +1));
     }
    }
    return a; 
}


There were a few other recurrence relations from other members of the OEIS community to describe this sequence, but unfortunately these were destroyed when the sequence got rejected.

This sequence satisfies the definition of a mathematical sequence, and it has a clearly defined recurrence relation. The term "artificial" in relation to the term "mathematical sequence" does not exist. (yet)

In other words, there is absolutely nothing artificial about it.  (yet)

Furthermore, this sequence is an important clue in the Collatz conjecture.

I already authored 5 other sequences in the OEIS that I talked about here and here.

Collatz Exit Sequence Denied


Largest Power of 2

Recently, I showed a formula for finding an odd integer n = 5k + 2 based on another odd integer k such that  3k + 1 = 2i where i is the largest power of 2 such that  2i < n. I called k a Collatz exit point and n a Collatz trap.

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.


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: A foursome square is an integer 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 n is the product of 2 distinct odd primes and 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.

9.8.16

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.

30.7.16

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;
}




14.7.16

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