[seqfan] Re: successive powers of 2 modulo n
RGWv
rgwv at rgwv.com
Fri Jun 10 15:30:14 CEST 2011
David,
Use PowerMod to calculate your terms, i.e.; PowerMod[2, k, 29].
Bob.
-----Original Message-----
From: David Scambler
Sent: Friday, June 10, 2011 3:22 AM
To: seqfan at list.seqfan.eu
Subject: [seqfan] successive powers of 2 modulo n
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