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.
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, 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, 24, 9, 10, 3, 60, 5, 6, 15, 64, 25, 18, 3, 68, 9, 30, 3, 40, 9, 10
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) = 1. For n=2, the only residues are 0 and 1 (each a fixed point), so a(2) = 2. 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. 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. 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) = 5. 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) = 6. 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 only 3 of the 7 trajectories reach a fixed point, so a(7)=3.
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, isok(r, n)); \\ Michel Marcus, May 02 2021
Formula
a(n) + A343722(n) = n. - Michel Marcus, May 02 2021