- (Generate a subset with starting index ki ,while starting index ki is less than or equal to n-1 shift it by k, add that subset to a table T, (return T if it reached the n*((n-1)/2)th index)
- If the last index of that subset is equal to n - ( k - 1 ) then go to (1.) with ki = 1, k = k, and table T;
- Else if the last index of that subset is equal to n - k then go to (1.) with ki = 0, k = k+1, and table T;
- Else if the last index of that subset is less than n and the row k is less than n/2 then shift new_ki = k-(n - ki) and go to (1.) with ki = new_ki , k = k, and table T;
- Return table T;
//Author: Marina Ibrishimova
//Purpose: Generate the first half of the multiplication table of Zn
//without actually computing the GCD(each_row_index*each_column_index, n)
function StopHammerTime(ki, k, n, table_so_far) {
var len = table_so_far.length;
var half_table_slots = n*((n-1)/2);
if(len == half_table_slots) {return;}
else {
while ( ki <= (n - 1)) {
table_so_far.push(ki);
ki = ki + k;
}
len = table_so_far.length;
var last_inset = table_so_far[len-1];
var k_dist = n - last_inset;
var new_ki = k - k_dist;
var n_k = k + 1;
if(last_inset == n-(k-1) && k < n/2) { StopHammerTime(1, k, n, table_so_far); }
else if(last_inset == n-k && k < n/2) { StopHammerTime(0, n_k , n, table_so_far); }
else if(last_inset < n && k < n/2){ StopHammerTime(new_ki, k, n, table_so_far); }
}
return table_so_far;
}
Generating powers of k mod n
The following is an algorithm for the case when GCD(k,n) = 1. Here is the algorithm for all cases.
- List the kth row of the multiplication table of Zn: for an entry aij at row i and column j of the multiplication table of Zn, if aij == (n-i) then the end of the ith row has been reached and also if i+ aij-1> n then aij = (i+aij-1) - n
- a Look up the value at initial index; b. Make that value the initial index; c. Save and Repeat a and b until the value equals 1
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Generate powers of k mod n where GCD(k,n) = 1,
generate the unique portion of row at k
of the multiplication table of Z sub n
---------------------------------------------------- */
function powers_of_k_mod(n,k)
{
var index = 0;
var perm_slot = k;
var count = 1;
var perm = new Array(); var powers = new Array();
perm = generate_permutation(n, k);
powers.push(1);
powers.push(perm_slot);
while(perm_slot != 1)
{
index = perm_slot;
perm_slot = perm[index];
powers.push(perm_slot);
}
return powers;
}
/* -----------------------------------------------
generate kth row of the multiplication table
of Z sub n
-------------------------------------------------- */
function generate_permutation(n, k)
{
var index = 0;
var permutation = new Array();
permutation.push(0);
while(index!=(n-k))
{
index = index + k;
if (index > n) {
index = index - n;
}
permutation.push(index);
}
return permutation;
}
For the case of when k = 2 I have several different variations of this algorithm.
I first described the most basic one in a post titled Phi Not Pi, but here's a better explanation of it.
/* -------------------------------------------------
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 mod n,
generate the unique portion of row at 2
of the exponentiation table of Z sub n
---------------------------------------------------- */
function powers_of_two_mod(n)
{
var index = 0;
var perm_slot = 2;
var count = 1;
var perm = new Array(); var powers = new Array();
perm = generate_permutation(n);
while(perm_slot != 1)
{
index = perm_slot;
perm_slot = perm[index];
powers.push(perm_slot);
}
return powers;
}
/* -----------------------------------------------
list all even integers smaller than n,
followed by all odd integers smaller than n:
this is 2nd row of the multiplication table of Z sub n
-------------------------------------------------- */
function generate_permutation(n)
{
var index = 0;
var permutation = new Array();
permutation.push(0);
while(index<n)
{
index = index + 2;
if (index == n-1) {
permutation.push(index);
index = 1;
}
permutation.push(index);
}
return permutation;
}
Moving onto a fancier variation, which takes into account the fact that the (n+1)/2 row of the exponentiation table mod n is equivalent to the 2 row of the exponentiation table 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 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;
}
So far all of these algorithms require the generation of a row of the multiplication table mod n but the one algorithm below does not. It is also slightly reminiscent of the algorithm behind the Collatz conjecture and again, it doesn't require modular arithmetc.
/* -------------------------------------------------
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;
}