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:

a_{1} = (n+1)/2 given an odd n

a_{i} = a_{i-1}/2 if a_{i-1} is even

a_{i} = (a_{i-1}-1)/2 + a_{1} if a_{i-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 Z

_{n} 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 Z

_{n}, 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.