A037179 Number of cycles when squaring modulo n-th prime.
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, 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, 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
Offset: 1
Keywords
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10000
- E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, On a digraph defined by squaring modulo n, Fibonacci Quart. 30 (Nov. 1992), 322-333. See p. 9.
- Thomas D. Rogers, The graph of the square mapping on the prime fields, Discrete Mathematics, Volume 148, Issues 1-3, 15 January 1996, Pages 317-324. See p. 4.
- Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 28 February 2004, Pages 219-240. See theorem 6 p. 6.
Programs
-
Mathematica
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 *)
-
PARI
rho(p) = {my(m = p-1); m >> valuation(m, 2);} a(n) = {my(r = rho(prime(n))) ; 1+ sumdiv(r, d, eulerphi(d)/znorder(Mod(2,d)));} \\ Michel Marcus, Jan 30 2016
Formula
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
Comments