[seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
Vladimir Shevelev
shevelev at bgu.ac.il
Sat Jul 24 05:38:04 CEST 2010
Phenomenon with the average depth=2 of a step in divisions method (in my version) is characterized
rather simply. Indeed, the average depth=(l_1+...+l_k)/k, where k=A179382(n), thus itis
ord_(2*n-1)(2)/A179382(n), and if this ratio is 2, then such numbers are 2*A179460-1. I have already written that the arithmetic sense of k=A179382(n) is the number of odd residues in {1,2,...,2^ord_(2*n-1)(2)} (considered in the reduced residue system modulo 2*n-1). Thus the observed phenomenon takes place for the numbers 2*n-1 for which the set {1,2,...,2^ord_(2*n-1)(2)} contains the same number of odd and even residues modulo 2*n-1. For other numbers (if n>1) always more even residues and the considered average depth of a step is more than 2, i.e., we have "adrenalin-numbers".
If anyone can estimate an upper (lower) density of such numbers?
Regards,
Vladimir
----- Original Message -----
From: Vladimir Shevelev <shevelev at bgu.ac.il>
Date: Friday, July 23, 2010 12:56
Subject: [seqfan] Re: An algorithm of calculation of multiplicative order of 2 mod n
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> 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
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
Shevelev Vladimir
More information about the SeqFan
mailing list