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,1

Comments

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

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.

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

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 *)

Prog

(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

Crossrefs

Cf. A000265,A037178, A037180.

Sequence in context: A078570 A295284 A292995 * A127971 A319290 A230516

Adjacent sequences: A037176 A037177 A037178 * A037180 A037181 A037182

Keyword

nonn

Author

Jud McCranie

Status

approved