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.

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