login
A048280
Length of longest run of consecutive quadratic residues mod prime(n).
4
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
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
Sequence in context: A352130 A035430 A167227 * A024695 A259195 A143997
KEYWORD
nonn
EXTENSIONS
Offset corrected to 1 and definition clarified by Jonathan Sondow Jul 20 2014
STATUS
approved