[seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
Vladimir Shevelev
shevelev at bgu.ac.il
Fri Jul 23 11:38:46 CEST 2010
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
More information about the SeqFan
mailing list