login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A097160 Greatest prime p such that there are n, but not n+1, consecutive quadratic residues mod p, or -1 if no such prime exists. 4
5, 17, 53, 193, 457, 2153 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

The most likely continuation (after 2153) is 4481, 9857, 25793, 60961, 132113, 324673. - Don Reble, Aug 02 2014 (see LINKS). - N. J. A. Sloane, Dec 11 2015

From David L. Harden: (Start)

"Proof that A097160(2)=17:

"Since the quadratic residues modulo 17 are 1,2,4,8,9,13,15 and 16, there are no 3 consecutive integers among these. Thus A097160(2)>=17.

"To show it is 17, we show there will be a run of 3 when p>17:

"Case 1. (2/p)=(3/p)=1. 1,2,3 works. (Also, 2,3,4 or 48,49,50 will work)

"Case 2. (2/p)=1 and (3/p)=-1. In this case, 8,9,10 works unless (5/p)=-1. 49,50,51 will work unless (17/p)=1. But then 15,16,17 works.

"Case 3. (2/p)=-1 and (3/p)=1. In this case, 3,4,5 works unless (5/p)=-1. But then 49/120, 169/120, 289/120 will work since 120 is invertible modulo p.

"Case 4. (2/p)=(3/p)=-1. Then 1/24, 25/24, 49/24 works. QED

Here the quadratic character of only 2 primes was used; for higher-index terms, more primes should be needed (how many?) and this promises to make computation (via these ideas) exponentially harder.

"One can attempt to carry out this kind of reasoning while eschewing fractions; then the chase for a run of quadratic residues is longer but one can obtain a universal upper bound on the onset of such a run of quadratic residues.

"Note that if the quadratic character of -1 is known, then a run of consecutive quadratic residues can include both negative and positive fractions (like -7/6, -1/6, 5/6, 11/6).

"Otherwise the help from knowing (-1/p) seems to be rather limited:

"If (-1/p)=-1, then a run of k quadratic nonresidues mod p can be turned into a run of k quadratic residues mod p by multiplying them by -1 and reversing their order. This allows the computation in this case to be that much easier. However, this also seems to make it harder for a prime p in A097160 to have (-1/p)=-1, as evidenced by the fact that all the terms included there are congruent to 1 mod 4.

"Problem: Are all terms in A097160 congruent to 1 mod 4?

"Also, beyond A097160(3)=53, all listed terms are congruent to 1 mod 8. Does this hold up (if so, why?), or is it just a result of how little computation has been done?" (End)

REFERENCES

Alfred Brauer, Ueber Sequenzen von Potenzresten, S.-B. Deutsch. Akad. Wiss. Berlin 1928, 9-16.

LINKS

Table of n, a(n) for n=1..6.

D. H. Lehmer and Emma Lehmer, On Runs of Residues, Proc. Amer. Math. Soc, Vol. 13, No. 1 (Feb., 1962), pp. 102-106.

Don Reble, Comments on A097160

EXAMPLE

Only the first three primes have no consecutive quadratic residues, so a(1) is the third prime, 5.

53 has three consecutive quadratic resides, but not four; and each larger prime has four consecutives.

MATHEMATICA

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_] := g[n] = f[ JacobiSymbol[ Range[ Prime[n] - 1], Prime[n]], 1][[1]]; g[1] = 1; a = Table[0, {30}]; Do[ a[[ g[n]]] = n, {n, 2556}]; Prime[a]

CROSSREFS

Cf. A097159, A097161.

Cf. A000236 and A000445 for higher-degree residues.

Sequence in context: A154992 A178828 A242429 * A149656 A146063 A146006

Adjacent sequences:  A097157 A097158 A097159 * A097161 A097162 A097163

KEYWORD

nonn,hard

AUTHOR

Robert G. Wilson v, Jul 28 2004

EXTENSIONS

The old values of a(7) and a(8) were unproved, while a(9) and a(10) were wrong (and are still unknown), according to email message from Don Reble received by N. J. A. Sloane, Dec 11 2015, see LINKS.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 25 14:40 EST 2021. Contains 341609 sequences. (Running on oeis4.)