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,7

Comments

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

Links

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

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

Example

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.

Prog

(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

Crossrefs

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

Sequence in context: A241658 A256719 A362209 * A035622 A112919 A019201

Adjacent sequences: A343719 A343720 A343721 * A343723 A343724 A343725

Keyword

nonn

Author

Jon E. Schoenfield, Apr 27 2021

Status

approved