A023153 Number of cycles of function f(x) = x^2 mod n.

1, 2, 2, 2, 2, 4, 3, 2, 3, 4, 3, 4, 3, 6, 4, 2, 2, 6, 4, 4, 6, 6, 3, 4, 3, 6, 4, 6, 4, 8, 6, 2, 6, 4, 6, 6, 4, 8, 6, 4, 3, 12, 7, 6, 6, 6, 4, 4, 7, 6, 4, 6, 3, 8, 6, 6, 8, 8, 3, 8, 6, 12, 10, 2, 6, 12, 6, 4, 6, 12, 7, 6, 4, 8, 6, 8, 10, 12, 6, 4, 5, 6, 4, 12, 4, 14, 8, 6, 3, 12, 10, 6, 12, 8, 8, 4, 3, 14, 10, 6

Offset

1,2

Comments

Not multiplicative; the smallest counterexample is a(63). - T. D. Noe, Nov 14 2006

References

Earle Blanton, Spencer Hurd and Judson McCranie, On the Digraph Defined by Squaring Mod m, When m Has Primitive Roots, Congressus Numerantium, vol. 82, 167-177, 1992.

Links

David W. Wilson, Table of n, a(n) for n=1..10000

Earle Blanton, Spencer Hurd and Judson McCranie, On the Digraph Defined by Squaring Modulo n, Fib. Quarterly, vol. 30, #4, 1992, 322-334.

J. J. Brennan and B. Geist, Analysis of Iterated Modular Exponentiation: The Orbits of x alpha mod N, Designs, Codes and Cryptography 13, 229-245 (1998) (specially Th. 6 and 7).

G. Chassé, Applications d'un corps fini dans lui-même, Publications mathématiques et informatique de Rennes, no. 4 (1985), p. 207-219; Math. Rev. 86e:11118.

Sean A. Irvine, Java program (github)

T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math. 148 (1996), 317-324.

Formula

In case (Z/nZ)^* is cyclic there is a formula (see Chasse and Rogers). Let C_m denote the cyclic group of order m. Let a(m) denote the number of cycles in the graph of C_m relative to the mapping f. Then the number of cycles equals a(m) = Sum_{d|n} phi(d)/ord_d(2). - Pieter Moree, Jul 04 2002

Mathematica

Table[Length[ConnectedComponents[Graph[Range[0, n-1], Table[UndirectedEdge[i, Mod[i^2, n]], {i, 0, n-1}]]]], {n, 100}] (* Keyang Li, Nov 04 2024 *)

Crossrefs

Cf. A023154-A023161 (cycles of the functions f(x)=x^k mod n for k=3..10).

Sequence in context: A367130 A064486 A153437 * A023159 A098983 A097576

Adjacent sequences: A023150 A023151 A023152 * A023154 A023155 A023156

Keyword

nonn

Author

David W. Wilson

Status

approved