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

Author

David W. Wilson

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A002307, A048281.

Programs

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

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

Extensions

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