A343720 -id:A343720 - 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.

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

Jon E. Schoenfield, Apr 27 2021

nonn

a(n) = 0 iff n is a term of A003401, that is, A000010(n) is a power of 2.

			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.

Michel Marcus, Table of n, a(n) for n = 1..2000

Cf. A003401, A004169, A279185, A343720, A343721.

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

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

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.

Original entry on oeis.org

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

Jon E. Schoenfield, Apr 26 2021

nonn

			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.

Michel Marcus, Table of n, a(n) for n = 1..2000

Cf. A277847, A343720, A343722.

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

a(n) + A343722(n) = n. - Michel Marcus, May 02 2021

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula