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

[Vladimir Shevelev]

Thus to get ord_(2n-1)(2) we have the standard algorithm of multiplications by 2 modulo n (by the definition) and the algorithm of divisions by 2 modulo n. It is asked, why I and other participants of the discussion have not immediately observed the essentially trivial Max's explanation? The answer is simple: because of "pits", when we have: A007814(x)>=2. For the number of pits for 2n-1 I get sequence: 0 1 1 1 1 3 3 1 1 5 1 3 5 5 7 1 1 3 (...) (more terms?). Further, I wonder what is the average "depth" of a step in divisions method? Astonishingly, I  get exactly 2 for many numbers 2n-1.
They are: 3 5 9 11 13 17 19 25 27 29 33(...) and more than 2 for 7 15 21 23 31 35(...). The latter I call "adrenalin-numbers". Please, more terms.

Regards,
Vladimir


----- Original Message -----
From: Vladimir Shevelev <shevelev at bgu.ac.il>
Date: Thursday, July 22, 2010 8:59
Subject: [seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> Of course, one can calculate ord_n(a) by this algorithm ((n,a)=1).
> Examples: 
> to calculate ord_10(3) we have
> 10+1   0  11
> 10+11 1    7
> 10+7   0  17
> 10+17 3    1
>  Thus ord_10(3)=1+3=4;
> to calculate ord_11(4) we have
> 11+1    1    3
> 11+14  0   25
> 11+25  1    9
> 11+9    1   5
> 11+5    2   1
>  Thus ord_11(4)=1+1+1+2=5.
> 
> Regards,
> Vladimir
> 
> 
> 
> 
> ----- Original Message -----
> From: Max Alekseyev <maxale at gmail.com>
> Date: Wednesday, July 21, 2010 23:05
> Subject: [seqfan] Re: An algorithm of calculation of 
> multiplicative order of 2 mod n
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> 
> > 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/
> > >
> > 
> > 
> > _______________________________________________
> > 
> > Seqfan Mailing list - http://list.seqfan.eu/
> > 
> 
>  Shevelev Vladimir‎
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎