A048280 Length of longest run of consecutive quadratic residues mod prime(n).

2, 2, 3, 3, 3, 3, 5, 4, 5, 4, 4, 4, 5, 5, 5, 3, 5, 5, 6, 7, 9, 6, 7, 5, 9, 7, 7, 6, 5, 5, 7, 8, 6, 5, 4, 7, 6, 6, 6, 6, 6, 6, 7, 9, 7, 6, 7, 7, 7, 5, 6, 7, 13, 7, 6, 7, 8, 7, 10, 6, 9, 9, 7, 11, 9, 5, 8, 9, 8, 6, 6, 8, 9, 6, 8, 8, 8, 5, 7, 13, 8, 7, 7, 9, 10, 8, 8, 9, 8, 8, 11, 13, 8, 8, 10, 8, 9, 8, 10, 7, 9, 9, 10, 10, 7, 9

Offset

1,1

Comments

0 and 1 are consecutive quadratic residues for any prime, so a(n) >= 2.

"Consecutive" allows wrap-around, so p-1 and 0 are consecutive. - Robert Israel, Jul 20 2014

A002307(n) is defined similarly, except that only positive reduced quadratic residues are counted. - Jonathan Sondow, Jul 20 2014

For longest runs of quadratic nonresidues, see A002308. - Jonathan Sondow, Jul 20 2014

Links

Robert Israel, Table of n, a(n) for n = 1..10000

P. Pollack and E. Treviño, The primes that Euclid forgot, Amer. Math. Monthly, 121 (2014), 433-437.

Enrique Treviño, Corrigendum to “On the maximum number of consecutive integers on which a character is constant”, Mosc. J. Comb. Number Theory 7 (2017), no. 3, 1-2.

Formula

a(n) < 2*sqrt(prime(n)) for n >= 1 (see Pollack and Treviño for n > 1). - Jonathan Sondow, Jul 20 2014

a(n) >= A002307(n). - Jonathan Sondow, Jul 20 2014

a(n) < 7 prime(n)^(1/4)log(prime(n)) for all n > 1, or a(n) < 3.2 prime(n)^(1/4)log(prime(n)) for n >= 10^13. - Enrique Treviño, Apr 16 2020

Example

For n = 7, prime(7) = 17 has consecutive quadratic residues 15,16,0,1,2, and no longer sequence of consecutive quadratic residues, so a(7)=5.

Maple

A:= proc(n) local P, res, nonres, nnr;
     P:= ithprime(n);
     res:= {seq(i^2, i=0..floor((P-1)/2)};
     nonres:= {$1..P-1} minus res;
     nnr:= nops(nonres);
     max(seq(nonres[i+1]-nonres[i]-1, i=1..nnr-1), nonres[1]-nonres[-1]+P-1)
end proc;
A(1):= 2:
seq(A(n), n=1..100); # Robert Israel, Jul 20 2014

Crossrefs

Cf. A002307, A048281.

Sequence in context: A352130 A035430 A167227 * A024695 A259195 A143997

Adjacent sequences: A048277 A048278 A048279 * A048281 A048282 A048283

Keyword

nonn

Author

David W. Wilson

Extensions

Offset corrected to 1 and definition clarified by Jonathan Sondow Jul 20 2014

Status

approved