|
| |
|
|
A128976
|
|
Number of cycles for the map LL:x->x^2-2 acting on Z/(2^n-1).
|
|
2
| |
|
|
2, 1, 1, 2, 2, 4, 6, 8, 6, 8, 14, 25, 36, 180, 76, 80, 66, 2068, 354, 7316
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,1
|
|
|
COMMENTS
| A cycle is the orbit of an element x of Z/(2^n-1) such x=LL^c(x) for some positive integer c, i.e. { x, LL(x), ..., LL^c(x)=x }.
|
|
|
LINKS
| Troy Vasiga and Jeffrey Shallit: On the iteration of certain quadratic maps over GF(p), Discrete Math. (277) 219-240.
|
|
|
FORMULA
| If p=2^n-1 is prime, then a(n) = 1/2 + sum_{d|2^(n-1)-1} eulerphi(d)/ordp(2,d)/2, where ordp(2,d) = min { e in N* | 2^e=1 (mod d) or 2^e=-1 (mod d) }
|
|
|
EXAMPLE
| a(0)=2 since fixed points 2 and -1 are the only cycles for LL on Z/(0) = Z;
a(1)=1 since Z/(1) = {0};
a(2)=1 since 2=-1 is a cycle of length 1 (fixed point) for LL on Z/(3) and LL(0)=-2=1, LL(1)=-1;
a(3)=2 since 3,4(=-3) -> 0 -> 5(=-2) -> {2} and 1 -> {6(=-1)} for LL acting on Z/(7);
a(5)=4 since {2}, {30}, {12,18} and {3,7,16,6} are the cycles for LL acting on Z/(31).
|
|
|
PROG
| (PARI) numcycles(q) = { local(Mq=2^q-1, v=vector(Mq+1), c=1, i, start, cyc=0); if(q<2, return(1+!q)); for( j=1, #v, if(v[j], next); i=j; start=c; until(v[i=1+((i-1)^2-2)%Mq], v[i]=c++); if(v[i]>start, cyc++)); cyc } A128976=vector(20, i, numcycles(i-1))
|
|
|
CROSSREFS
| Cf. A003010.
Sequence in context: A045870 A036863 A083698 * A199627 A153902 A046772
Adjacent sequences: A128973 A128974 A128975 * A128977 A128978 A128979
|
|
|
KEYWORD
| more,nonn
|
|
|
AUTHOR
| M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Apr 29 2007, corrected May 19 2007
|
| |
|
|
