cp's OEIS Frontend

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.

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