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

Vladimir Shevelev shevelev at bgu.ac.il
Sat Jul 24 05:41:58 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 it is 
ord_(2*n-1)(2)/A179382(n), and if this ratio is 2, then such numbers are 2*A179460(n)-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