login
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
OFFSET
1,2
LINKS
FORMULA
a(n) + A343722(n) = n. - Michel Marcus, May 02 2021
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
a(n) = sum(r=0, n-1, isok(r, n)); \\ Michel Marcus, May 02 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Jon E. Schoenfield, Apr 26 2021
STATUS
approved