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
Keywords
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.
Programs
-
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 *)
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
Comments