login
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

%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