A037178 - OEIS

%I #34 Feb 03 2025 22:47:21

%S 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,

%T 18,3,6,12,8,22,36,20,12,54,82,14,11,12,36,2,21,30,12,36,28,18,28,24,

%U 4,100,1,130,66,36,22,12,46,9,24,20,12,39,20,6,172,28,10,178,60,10,18

%N Longest cycle when squaring modulo n-th prime.

%C 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

%H T. D. Noe, <a href="/A037178/b037178.txt">Table of n, a(n) for n=1..10000</a>

%H 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.

%H Haifeng Xu, <a href="http://arxiv.org/abs/1601.06509">The largest cycles consist by the quadratic residues and Fermat primes</a>, arXiv:1601.06509 [math.NT], 2016. See table on page 2.

%F 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

%F a(n) = A007733(A002322(prime(n))). - _Michel Marcus_, Jan 28 2016

%F a(n) = A256608(prime(n)).

%t 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_ *)

%o (PARI) a(n) = {ppn = prime(n) - 1; k = ppn >> valuation(ppn, 2); znorder(Mod(2, k));} \\ _Michel Marcus_, Nov 11 2015

%o (PARI) rpsi(n) = lcm(znstar(n)[2]); \\ A002322

%o pb(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ A007733

%o a(n) = pb(rpsi(prime(n))); \\ _Michel Marcus_, Jan 28 2016

%Y Cf. A002322, A007733, A256608.

%Y Cf. A019434, A039687, A050527, A141305.

%Y Cf. A037179, A037180.

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

%K nonn,changed

%O 1,4

%A _Jud McCranie_