%I #12 May 02 2021 12:05:06
%S 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,
%T 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,
%U 24,9,10,3,60,5,6,15,64,25,18,3,68,9,30,3,40,9,10
%N 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.
%H Michel Marcus, <a href="/A343721/b343721.txt">Table of n, a(n) for n = 1..2000</a>
%F a(n) + A343722(n) = n. - _Michel Marcus_, May 02 2021
%e 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.
%e For n=1, the only residue mod n is 0 (a fixed point), so a(1) = 1.
%e For n=2, the only residues are 0 and 1 (each a fixed point), so a(2) = 2.
%e 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.
%e 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.
%e For n=5, we have
%e 0 -> 0
%e 1 -> 1
%e 2 -> 4 -> 1 -> 1
%e 3 -> 4 -> 1 -> 1
%e 4 -> 1 -> 1
%e (each ending at a fixed point), so a(5) = 5.
%e For n=6, we have
%e 0 -> 0
%e 1 -> 1
%e 2 -> 4 -> 4
%e 3 -> 3
%e 4 -> 4
%e 5 -> 1 -> 1
%e (each ending at a fixed point), so a(6) = 6.
%e For n=7, however, we have
%e 0 -> 0
%e 1 -> 1
%e 2 -> 4 -> 2 -> ... (a loop)
%e 3 -> 2 -> 4 -> 2 -> ... (a loop)
%e 4 -> 2 -> 4 -> ... (a loop)
%e 5 -> 4 -> 2 -> 4 -> ... (a loop)
%e 6 -> 1 -> 1
%e so only 3 of the 7 trajectories reach a fixed point, so a(7)=3.
%o (PARI) pos(list, r) = forstep (k=#list, 1, -1, if (list[k] == r, return (#list - k + 1)););
%o 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
%o a(n) = sum(r=0, n-1, isok(r, n)); \\ _Michel Marcus_, May 02 2021
%Y Cf. A277847, A343720, A343722.
%K nonn
%O 1,2
%A _Jon E. Schoenfield_, Apr 26 2021