[seqfan] An algorithm of calculation of multiplicative order of 2 mod n
Vladimir Shevelev
shevelev at bgu.ac.il
Tue Jul 20 20:18:11 CEST 2010
Dear Seq Fan,
I would like to present an easy (till now-conjectural!) algorithm of calculation of multiplicative order of 2 mod n (n arbitrary positive odd number). It is based on trivial calculation of A007814(x) in base 2.
Step1. l(1)=A007814(n+1), m(1)=(n+1)/2^l(1);
Step i(i>=2). l(i)=A007814(n+m(i-1)), m(i)=(n+m(i-1))/2^l(i);
The process ends when m=1.
Now we have: A002326(n)=l(1)+...+l(k).
Example (here A007814=a(n)).
a(17+1)=1, (17+1)/2=9;
a(17+9)=1, (17+9)/2=13;
a(17+13)=1, (17+13)/2=15;
a(17+15)=5, (17+15)/(2^5)=1.
Thus A002327(17)=1+1+1+5=8.
Regards,
Vladimir
Shevelev Vladimir
More information about the SeqFan
mailing list