cp's OEIS Frontend

A343722 a(n) is the number of starting residues r modulo n from which repeated iterations of the mapping r -> r^2 mod n never reach a fixed point.

%I A343722 #24 May 02 2021 12:05:28
%S A343722 0,0,0,0,0,0,4,0,4,0,8,0,8,8,0,0,0,8,16,0,12,16,20,0,16,16,16,16,24,0,
%T A343722 28,0,24,0,20,16,32,32,24,0,32,24,40,32,20,40,44,0,40,32,0,32,48,32,
%U A343722 40,32,48,48,56,0,56,56,48,0,40,48,64,0,60,40,68,32
%N A343722 a(n) is the number of starting residues r modulo n from which repeated iterations of the mapping r -> r^2 mod n never reach a fixed point.
%C A343722 a(n) = 0 iff n is a term of A003401, that is, A000010(n) is a power of 2.
%H A343722 Michel Marcus, <a href="/A343722/b343722.txt">Table of n, a(n) for n = 1..2000</a>
%F A343722 a(n) is the number of terms of n-th row of A279185 that are greater than 1. - _Pontus von Brömssen_, Apr 27 2021
%F A343722 a(n) + A343721(n) = n. - _Michel Marcus_, May 02 2021
%e A343722 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 A343722 For n=1, the only residue mod n is 0 (a fixed point), so a(1) = 0.
%e A343722 For n=2, the only residues are 0 and 1 (each a fixed point), so a(2) = 0.
%e A343722 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) = 0.
%e A343722 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) = 0.
%e A343722 For n=5, we have
%e A343722   0 -> 0
%e A343722   1 -> 1
%e A343722   2 -> 4 -> 1 -> 1
%e A343722   3 -> 4 -> 1 -> 1
%e A343722   4 -> 1 -> 1
%e A343722 (each ending at a fixed point), so a(5) = 0.
%e A343722 For n=6, we have
%e A343722   0 -> 0
%e A343722   1 -> 1
%e A343722   2 -> 4 -> 4
%e A343722   3 -> 3
%e A343722   4 -> 4
%e A343722   5 -> 1 -> 1
%e A343722 (each ending at a fixed point), so a(6) = 0.
%e A343722 For n=7, however, we have
%e A343722   0 -> 0
%e A343722   1 -> 1
%e A343722   2 -> 4 -> 2 -> ...       (a loop)
%e A343722   3 -> 2 -> 4 -> 2 -> ...  (a loop)
%e A343722   4 -> 2 -> 4 -> ...       (a loop)
%e A343722   5 -> 4 -> 2 -> 4 -> ...  (a loop)
%e A343722   6 -> 1 -> 1
%e A343722 so 4 of the 7 trajectories never reach a fixed point, so a(7)=4.
%o A343722 (PARI) pos(list, r) = forstep (k=#list, 1, -1, if (list[k] == r, return (#list - k + 1)););
%o A343722 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 A343722 a(n) = sum(r=0, n-1, 1 - isok(r, n)); \\ _Michel Marcus_, May 02 2021
%Y A343722 Cf. A003401, A004169, A279185, A343720, A343721.
%K A343722 nonn
%O A343722 1,7
%A A343722 _Jon E. Schoenfield_, Apr 27 2021