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