[seqfan] successive powers of 2 modulo n

David Scambler dscambler at bmm.com
Fri Jun 10 09:22:11 CEST 2011


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?




More information about the SeqFan mailing list