A002308 -id:A002308 - cp's OEIS frontend

A002307 Consecutive quadratic residues mod p: a(n) is the maximal number of positive reduced quadratic residues which appear consecutively for n-th prime.

1, 1, 1, 2, 3, 2, 2, 4, 4, 4, 4, 4, 3, 5, 4, 3, 5, 5, 6, 6, 4, 6, 7, 4, 4, 7, 7, 6, 5, 5, 7, 8, 6, 5, 4, 7, 6, 6, 6, 6, 6, 6, 6, 4, 7, 6, 7, 7, 7, 5, 6, 6, 6, 7, 6, 7, 8, 7, 10, 6, 9, 9, 7, 10, 5, 5, 8, 5, 8, 6, 6, 8, 9, 6, 8, 8, 8, 5, 7, 6, 8, 7, 6, 7, 10, 8, 8, 5, 8, 8, 11, 12, 8, 8, 10, 8, 9, 8, 10, 7, 9, 9, 10, 10, 7, 6, 9

Offset: 1

N. J. A. Sloane

When prime(n) == 3 (mod 4), then a(n) = A002308(n). - T. D. Noe, Apr 03 2007

A048280(n) is defined similarly, except that reduced quadratic residues equal to 0 are also included. - Jonathan Sondow, Jul 20 2014

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
A. A. Bennett, Consecutive quadratic residues, Bull. Amer. Math. Soc., 32 (1926), 283-284.

Cf. A002308, A048280, A097159.

f[l_, a_] := Module[{A = Split[l], B}, B = Last[ Sort[ Cases[A, x : {a ..} :> {Length[x], Position[A, x][[1, 1]]}]]]; {First[B], Length[ Flatten[ Take[A, Last[B] - 1]]] + 1}]; g[n_] := f[ JacobiSymbol[ Range[ Prime[n] - 1], Prime[n]], 1][[1]]; Table[ g[n], {n, 2, 102}] (* Robert G. Wilson v, Jul 28 2004 *)

a(n) <= A048280(n) < 2*sqrt(prime(n)). - Jonathan Sondow, Jul 20 2014

More terms from David W. Wilson

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

Original entry on oeis.org

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

David W. Wilson

nonn

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

			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.

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.

Cf. A002307, A048281.

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

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

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

A124882 Maximum number of distinct squares in arithmetic progression modulo prime(n).

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Nov 13 2006

nonn

For the natural numbers, it is well known that four squares cannot be in AP. Brown shows that this is not the case for modular arithmetic. There is no limit to the number of squares in AP modulo a prime: for the n-th prime pseudosquare A002223(n), the numbers 0,1,2,...,prime(n+1)-1 are squares in AP mod A002223(n).
From Travis Scott, May 28 2022: (Start)
Consider that a quadratic residue coloring of Z/pZ by R,N is essentially a binary string in a necklace of p strings in a chord of phi(p) necklaces.
Our exhaustive search for APs of distinct squares, as described by the original Mathematica program, fixes two of the R (say r1,r2) and permutes an equivalent string x -> Ax+b (with A = r2-r1 and b = r1) to count the first run of R on that string. We can reduce our search space by two symmetries:
I. R * color(x) = color(x) and N * color(x) = color^-1(x) implies that each Ax+b maps every cyclic k-term AP to a k-AP of the same color if A is a residue or to a k-AP of the opposite color if A is a nonresidue--we don't need to count runs in both colors for more than one A (or in one color for more than two A if those A transverse R,N).
II. p == +-1 (mod 4) induces color(-x) = color^+-1(x) implies that every k-AP running counterclockwise from 0 maps to a k-AP of the same or opposite color running clockwise from 0--we also don't need to count both colors in both halves of the same necklace. (Note, however, that for +1 the first and last k-APs counted from 0 in either direction overlap the mirrors at 0 and p/2 by k-1 and k.)
By I and II then, to certify a(n) for all differences on Z/pZ* and from all starting points on Z/pZ, it suffices to count the runs of R and N on the unpermuted coloring over the interval [0, p/2), weighting the first and last counts to 2k-1 and 2k if p == 1 (mod 4). (End)

			Consider numbers modulo 13, the 6th prime. The squares mod 13 are 0,1,3,4,9,10,12. Exhaustive search finds that the four numbers 1,9,17,25 are in AP and are also distinct squares modulo 13. Hence a(6)=4. There are two other APs of squares having the same length: 4,10,16,22 and 10,12,14,16.
From _Travis Scott_, May 28 2022: (Start)
Taking the same example on Z/13Z but with no information other than the residues < 13/2 (0,1,3,4) and the polarity of 13 (+) we find that the string RRNRRNN adjusted to (2k-1)RRR N RR NNNN(2k) has no longer run in any color than NNNN so a(6)=4. We can also use the N values of that run to show a maximal AP of squares mod 13 starting from every residue:
   2 * 5,6,7,8 = 10,12, 1, 3 = 10,12,14,16
   5 * 5,6,7,8 = 12, 4, 9, 1 = 12,17,22,27
   6 * 5,6,7,8 =  4,10, 3, 9 =  4,10,16,22
   7 * 5,6,7,8 =  9, 3,10, 4 =  9,16,23,30
   8 * 5,6,7,8 =  1, 9, 4,12 =  1, 9,17,25
  11 * 5,6,7,8 =  3, 1,12,10 =  3,14,25,36. (End)

K. S. Brown, Squares in Arithmetic Progression (mod p)
Pablo Saez, X. Vidaux, and M. Vsemirnov, Optimal bounds for Buchi's problem in modular arithmetic, Journal of Number Theory Volume 149, April 2015, Pages 368-403.

t=Table[p=Prime[n]; sqs=Sort[Mod[Range[0,(p-1)/2]^2,p]]; kMx=0; Do[If[i!=j, df=sqs[[j]]-sqs[[i]]; k=2; While[MemberQ[sqs, Mod[sqs[[i]]+k*df,p]], k++ ]; k--; If[k>kMx, kMx=k]], {i,Length[sqs]}, {j,Length[sqs]}]; kMx+1, {n,2,PrimePi[617]}]; Join[{2},t]
(* alternate program *)
Qres1C=Compile[{{x,_Integer,1},{q,_Integer,0}},Module[{s=0,z=0,i=2},While[x[[i]]==x[[i-1]],i++];z=2i-1;s=i;While[i"C",RuntimeAttributes->{Listable},Parallelization->True];
QresIC=Compile[{{x,_Integer,1},{q,_Integer,0}},Module[{s=2,z=2},Do[If[x[[i]]==x[[i-1]],s++,If[s>z,z=s];s=1],{i,2,q}];If[s>z,z=s];z],CompilationTarget->"C",RuntimeAttributes->{Listable},Parallelization->True];
{2}~Join~Table[If[Mod[p,4]==1,Qres1C[#,(p+1)/2],QresIC[#,(p-1)/2]]&@Unitize[PowerMod[Range[(p-1)/2],(p-1)/2,p]-1],{p,Prime@Range[2,6543]}]
(* Travis Scott, May 28 2022 Accelerated by symmetry per comment. *)

a(n) = max(A048280(n), A002308(n)).

cp's OEIS Frontend

A002307 Consecutive quadratic residues mod p: a(n) is the maximal number of positive reduced quadratic residues which appear consecutively for n-th prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A124882 Maximum number of distinct squares in arithmetic progression modulo prime(n).

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A129201 Smallest prime p such that there are n consecutive quadratic nonresidues mod p.

Views

Author

Keywords

Comments

Crossrefs