[seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n

[Max Alekseyev]

The algorithm iteratively performs divisions by 2 modulo n.
It starts with n+1 == 1 (mod n) and ends with 1. The total number of
divisions k is then nothing else but the multiplicative order of 2 mod
n.

Max

On Tue, Jul 20, 2010 at 2:18 PM, Vladimir Shevelev <shevelev at bgu.ac.il> wrote:
> 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‎
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>