A037178 Longest cycle when squaring modulo n-th prime.

1, 1, 1, 2, 4, 2, 1, 6, 10, 3, 4, 6, 4, 6, 11, 12, 28, 4, 10, 12, 6, 12, 20, 10, 2, 20, 8, 52, 18, 3, 6, 12, 8, 22, 36, 20, 12, 54, 82, 14, 11, 12, 36, 2, 21, 30, 12, 36, 28, 18, 28, 24, 4, 100, 1, 130, 66, 36, 22, 12, 46, 9, 24, 20, 12, 39, 20, 6, 172, 28, 10, 178, 60, 10, 18

Offset

1,4

Comments

a(n)=1 for Fermat primes, A019434. a(n)=2 for primes in A039687. a(n)=3 for primes in A050527. Sequence A141305 gives those primes p > 3 having the longest possible cycle, (p-3)/2. - T. D. Noe, Jun 24 2008

Links

T. D. Noe, 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.

Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016. See table on page 2.

Formula

Let p=prime(n) and k=A000265(p-1), the odd part of p-1. Then a(n) = ord(2,k), that is, the smallest positive integer x such that 2^x = 1 (mod k). - T. D. Noe, Jun 24 2008

a(n) = A007733(A002322(prime(n))). - Michel Marcus, Jan 28 2016

Mathematica

a[n_] := Module[{p = Prime[n], k}, k = (p-1)/2^IntegerExponent[p-1, 2]; MultiplicativeOrder[2, k]]; Array[a, 100] (* Jean-François Alcover, Jan 28 2016, after T. D. Noe *)

Prog

(PARI) a(n) = {ppn = prime(n) - 1; k = ppn >> valuation(ppn, 2); znorder(Mod(2, k)); } \\ Michel Marcus, Nov 11 2015
(PARI) rpsi(n) = lcm(znstar(n)[2]); \\ A002322
pb(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ A007733
a(n) = pb(rpsi(prime(n))); \\ Michel Marcus, Jan 28 2016

Crossrefs

Cf. A019434, A039687, A050527, A141305.

Cf. A037179, A037180.

a(n) = maximal entry in row p of A278185.

Sequence in context: A105791 A116515 A303118 * A352650 A364038 A328192

Adjacent sequences: A037175 A037176 A037177 * A037179 A037180 A037181

Keyword

nonn

Author

Jud McCranie

Status

approved