cp's OEIS Frontend

A037179 Number of cycles when squaring modulo n-th prime.

%I A037179 #36 Feb 02 2025 20:10:16
%S A037179 2,2,2,3,3,3,2,4,3,4,6,4,3,7,4,3,3,6,6,7,4,6,4,3,3,4,9,3,5,4,14,8,4,7,
%T A037179 3,9,6,6,3,5,10,9,6,3,6,9,16,6,6,6,3,10,6,5,2,3,3,12,7,7,7,10,14,15,6,
%U A037179 4,15,7,3,6,3,3,6,15,21,4,4,9,4,9,6,16,12,5,19,13,4,6,7,16,10,4,7,11,6
%N A037179 Number of cycles when squaring modulo n-th prime.
%C A037179 Note that Rogers and Shallit give the formula for F*p and Rogers has a table with a(n)-1. - _Michel Marcus_, Jan 30 2016
%H A037179 Amiram Eldar, <a href="/A037179/b037179.txt">Table of n, a(n) for n = 1..10000</a>
%H A037179 E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/30-4/blanton.pdf">On a digraph defined by squaring modulo n</a>, Fibonacci Quart. 30 (Nov. 1992), 322-333. See p. 9.
%H A037179 Thomas D. Rogers, <a href="http://dx.doi.org/10.1016/0012-365X(94)00250-M">The graph of the square mapping on the prime fields</a>, Discrete Mathematics, Volume 148, Issues 1-3, 15 January 1996, Pages 317-324. See p. 4.
%H A037179 Troy Vasiga and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00158-4">On the iteration of certain quadratic maps over GF(p)</a>, Discrete Mathematics, Volume 277, Issues 1-3, 28 February 2004, Pages 219-240. See theorem 6 p. 6.
%F A037179 a(n) = 1+ Sum_{d|rho} phi(d)/ord(2,d) with rho the largest odd factor of prime(n)-1 (rho = A000265(p-1)). The 1 corresponds to the sink 0. - _Michel Marcus_, Jan 30 2016
%t A037179 odd[n_] := n/2^IntegerExponent[n,2]; a[n_] := 1 + DivisorSum[odd[Prime[n]-1], EulerPhi[#]/MultiplicativeOrder[2, #] &]; Array[a, 100] (* _Amiram Eldar_, Aug 29 2023 *)
%o A037179 (PARI) rho(p) = {my(m = p-1); m >> valuation(m, 2);}
%o A037179 a(n) = {my(r = rho(prime(n))) ; 1+ sumdiv(r, d, eulerphi(d)/znorder(Mod(2,d)));} \\ _Michel Marcus_, Jan 30 2016
%Y A037179 Cf. A000265, A037178, A037180.
%K A037179 nonn
%O A037179 1,1
%A A037179 _Jud McCranie_