23.2.17

Generating Powers of 2 Again

While looking into proving the algorithm I described here, I stumbled upon yet another algorithm for generating powers of 2.

This new algorithm is based on the following recurrence relation:

a1 = (n+1)/2        given an odd n  
ai = ai-1/2              if ai-1 is even
ai = (ai-1-1)/2 + a1 if ai-1 is odd

I claim that the recurrence relation above generates all powers of (n+1)/2 mod n in consecutive order and all powers of 2 mod n in reverse order.

This follows from the first part of the algorithm that I previously described, namely the claim below:

Claim: Given an odd integer n and k = (n+1)/2, then all consecutive multiples of k mod n, namely 1*k mod n, 2*k mod n, 3*k mod n,..., (n-2)*k, (n-1)*k, are equal to k, 1,  k + 1, 2,  k + 2,  3, k + 3, .... , n-1,  k - 1 respectively.

Proof:
Since n is an odd integer then Zn is a commutative ring closed under multiplication and addition with an identity element and so the following algebraic expressions hold.

Since k = (n+1)/2, then 2*k mod n = 2(n+1)/2 mod n = n+1 mod n and since n mod n = 0 then
2*k mod n = 1 mod n.

Similarly for all even multiples x of k: x*k = x/2.

On the other hand, 3*k mod n = ((n+1)/2  + (n+1)/2  + (n+1)/2) mod n
                                                 = (2(n+1)/2 + (n+1)/2) mod n
                                                 = 2(n+1)/2 mod n + (n+1)/2 mod n
                                                 = 1 mod n + (n+1)/2 mod n
                                                 = (1 +  (n+1)/2) mod n.

Similarly, for all odd multiples y of k: y*k = (n+1)/2 + (y - 1)/2
.'.

The index of each term in the sequence k, 1,  k + 1, 2,  k + 2,  3, k + 3, .... , n-1,  k - 1 , which is essentially the ((n+1)/2)th row of the multiplication table of Zn, reveals a few ways of finding powers of 2 mod n.

My previous algorithm for generating consecutive powers of 2 mod n in reverse order required the explicit generation of this particular row but the recurrence relation for the new algorithm that I described in the beginning of this post does not.

I implemented the new algorithm in Javascript below for reference.

/* -------------------------------------------------  
 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_again(n)
{
 var k = (n+1)/2;
 var halfie = k;
 var powers = new Array();
 do{
    powers.push(k); 
    if (k%2 == 0)
    {k = k/2;}
    else
    {k = ((k-1)/2)+halfie;}
   }while(k != 1)
 return powers;
}

And embedded bellow is a demo.



This algorithm is reminiscent of the algorithm behind the Collatz conjecture.