Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #37 Jan 05 2025 19:51:34
%S 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,
%T 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,
%U 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
%N Number of cycles of function f(x) = x^2 mod n.
%C Not multiplicative; the smallest counterexample is a(63). - _T. D. Noe_, Nov 14 2006
%D 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.
%H David W. Wilson, <a href="/A023153/b023153.txt">Table of n, a(n) for n=1..10000</a>
%H Earle Blanton, Spencer Hurd and Judson McCranie, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/30-4/blanton.pdf">On the Digraph Defined by Squaring Modulo n</a>, Fib. Quarterly, vol. 30, #4, 1992, 322-334.
%H J. J. Brennan and B. Geist, <a href="https://doi.org/10.1023/A:1008289605486">Analysis of Iterated Modular Exponentiation: The Orbits of x alpha mod N</a>, Designs, Codes and Cryptography 13, 229-245 (1998) (specially Th. 6 and 7).
%H G. Chassé, <a href="http://www.numdam.org/item/PSMIR_1985___4_207_0/">Applications d'un corps fini dans lui-même</a>, Publications mathématiques et informatique de Rennes, no. 4 (1985), p. 207-219; Math. Rev. 86e:11118.
%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a023/A023153.java">Java program</a> (github)
%H T. D. Rogers, <a href="https://doi.org/10.1016/0012-365X(94)00250-M">The graph of the square mapping on the prime fields</a>, Discrete Math. 148 (1996), 317-324.
%F 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
%t 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 *)
%Y Cf. A023154-A023161 (cycles of the functions f(x)=x^k mod n for k=3..10).
%K nonn,changed
%O 1,2
%A _David W. Wilson_