A097160 - OEIS

%I #27 Oct 25 2017 05:10:45

%S 5,17,53,193,457,2153

%N Greatest prime p such that there are n, but not n+1, consecutive quadratic residues mod p, or -1 if no such prime exists.

%C 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

%C From _David L. Harden_: (Start)

%C "Proof that A097160(2)=17:

%C "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.

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

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

%C "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.

%C "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.

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

%C 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.

%C "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.

%C "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).

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

%C "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.

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

%C "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)

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

%H D. H. Lehmer and Emma Lehmer, <a href="http://dx.doi.org/10.1090/S0002-9939-1962-0138582-6">On Runs of Residues</a>, Proc. Amer. Math. Soc, Vol. 13, No. 1 (Feb., 1962), pp. 102-106.

%H Don Reble, <a href="/A097160/a097160.txt">Comments on A097160</a>

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

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

%t 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]

%Y Cf. A097159, A097161.

%Y Cf. A000236 and A000445 for higher-degree residues.

%K nonn,hard

%O 1,1

%A _Robert G. Wilson v_, Jul 28 2004

%E 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.