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.
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, 28, 0, 24, 0, 20, 16, 32, 32, 24, 0, 32, 24, 40, 32, 20, 40, 44, 0, 40, 32, 0, 32, 48, 32, 40, 32, 48, 48, 56, 0, 56, 56, 48, 0, 40, 48, 64, 0, 60, 40, 68, 32
Offset: 1
Keywords
Examples
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) = 0. For n=2, the only residues are 0 and 1 (each a fixed point), so a(2) = 0. 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. 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. 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) = 0. 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) = 0. 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 4 of the 7 trajectories never reach a fixed point, so a(7)=4.
Links
- Michel Marcus, Table of n, a(n) for n = 1..2000
Programs
-
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, 1 - isok(r, n)); \\ Michel Marcus, May 02 2021
Formula
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
a(n) + A343721(n) = n. - Michel Marcus, May 02 2021
Comments