|
|
A343721
|
|
a(n) is the number of starting residues r modulo n from which repeated iterations of the mapping r -> r^2 mod n reach a fixed point.
|
|
2
|
|
|
1, 2, 3, 4, 5, 6, 3, 8, 5, 10, 3, 12, 5, 6, 15, 16, 17, 10, 3, 20, 9, 6, 3, 24, 9, 10, 11, 12, 5, 30, 3, 32, 9, 34, 15, 20, 5, 6, 15, 40, 9, 18, 3, 12, 25, 6, 3, 48, 9, 18, 51, 20, 5, 22, 15, 24, 9, 10, 3, 60, 5, 6, 15, 64, 25, 18, 3, 68, 9, 30, 3, 40, 9, 10
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For every n >= 1, the residue r = 0 is a fixed point under the mapping r -> r^2 mod n, since we have 0 -> 0^2 mod n = 0. Also, for every n >= 2, the residue r = 1 is a fixed point, since we have 1 -> 1^2 mod n = 1.
For n=1, the only residue mod n is 0 (a fixed point), so a(1) = 1.
For n=2, the only residues are 0 and 1 (each a fixed point), so a(2) = 2.
For n=3, the only residue other than 0 and 1 is 2; 2 -> 2^2 mod 3 = 4 mod 3 = 1, a fixed point, so a(3) = 3.
For n=4, we have 0 -> 0, 1 -> 1, 2 -> 2^2 mod 4 = 4 mod 4 = 0, and 3 -> 3^2 mod 4 = 9 mod 4 = 1, each trajectory ending at a fixed point, so a(4) = 4.
For n=5, we have
0 -> 0
1 -> 1
2 -> 4 -> 1 -> 1
3 -> 4 -> 1 -> 1
4 -> 1 -> 1
(each ending at a fixed point), so a(5) = 5.
For n=6, we have
0 -> 0
1 -> 1
2 -> 4 -> 4
3 -> 3
4 -> 4
5 -> 1 -> 1
(each ending at a fixed point), so a(6) = 6.
For n=7, however, we have
0 -> 0
1 -> 1
2 -> 4 -> 2 -> ... (a loop)
3 -> 2 -> 4 -> 2 -> ... (a loop)
4 -> 2 -> 4 -> ... (a loop)
5 -> 4 -> 2 -> 4 -> ... (a loop)
6 -> 1 -> 1
so only 3 of the 7 trajectories reach a fixed point, so a(7)=3.
|
|
PROG
|
(PARI) pos(list, r) = forstep (k=#list, 1, -1, if (list[k] == r, return (#list - k + 1)); );
isok(r, n) = {my(list = List()); listput(list, r); for (k=1, oo, r = lift(Mod(r, n)^2); my(i = pos(list, r)); if (i==1, return (1)); if (i>1, return(0)); listput(list, r); ); } \\ reaches a fixed point
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|