[seqfan] Re: successive powers of 2 modulo n
Jack Brennen
jfb at brennen.net
Sat Jun 11 05:59:22 CEST 2011
Just thought I'd point out that the cycle length is immediately computable
using PARI/GP, like so:
for(i=1,21,print(i," ",znorder(Mod(2,i/bitand(i,-i)))));
which gives your a(n) numbers from below.
Note that i/bitand(i,-i) is just a tricky way to divide all powers of 2 out of i.
On 6/10/2011 12:22 AM, David Scambler wrote:
> I am just playing around with this - not sure if it is of interest to others.
>
> Take the successive powers of 2 modulo n and the sequence apparently always enters a cycle.
> Is this true? Proof?
>
> e.g. Successive powers of 2 modulo 7 -> 1 2 4 1 2 4 1 2 4 1 2 4 ... - a cycle of length 3.
>
> For some numbers n the cycle length is n-1 e.g. moduli 2,3,5,11,13,19,29... have cycle lengths 1,2,4,10,12,18,28... respectively.
> Is this the maximum length?
>
> For n>= 1 the cycle lengths are
>
> a(n) = 1,1,2,1,4,2,3,1,6,4,10,2,12,3,4,1,8,6,18,4,6, ...
>
> And finally,
>
> Is there an efficient way to calculate successive 2^k mod n without actually evaluating 2^k and dividing by n?
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
More information about the SeqFan
mailing list