A097159 -id:A097159 - 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

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.

Original entry on oeis.org

5, 17, 53, 193, 457, 2153

Offset: 1

Robert G. Wilson v, Jul 28 2004

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)

			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.

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

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

Cf. A097159, A097161.

Cf. A000236 and A000445 for higher-degree residues.

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]

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.

A097161 Number of primes modulo which the largest number of consecutive quadratic residues is n.

Original entry on oeis.org

3, 3, 3, 11, 12, 34, 54, 97, 180, 351

Offset: 1

Robert G. Wilson v, Jul 29 2004

nonn

I am not sure how many of these entries have been proved to be correct. See comments in A097160. - N. J. A. Sloane, Jan 01 2007

			7, 13 & 17 have exactly two consecutive quadratic residues.
11, 41 & 53 have exactly three consecutive quadratic residues.
19, 23, 29, 31, 37, 47, 73, 89, 97, 149 & 193 have exactly four consecutive quadratic residues.
43, 59, 61, 109, 113, 139, 229, 313, 317, 337, 397 & 457 have exactly five consecutive quadratic residues.
67, 71, 79, 107, 137, 157, 163, 167, 173, 179, 181, 191, 199, 233, 239, 241, 257, 281, 349, 353, 373, 409, 431, 577, 601, 617, 641, 769, 797, 857, 881, 1049, 1373 & 2153 have exactly six consecutive quadratic residues.

Cf. A097159, A097160.

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

Original entry on oeis.org

2, 3, 5, 11, 13, 41, 53, 83, 131, 269, 109, 467, 421, 1907, 1607, 2543, 1559, 5443, 5711, 8867, 21319, 15401, 8941, 20747, 68903, 136223, 107119, 65129, 13381, 52361, 31391

Offset: 0

T. D. Noe, Apr 03 2007

nonn

Additional terms less than 10^6: a(32)=998423, a(33)=661049, a(35)=298483, a(36)=365509, a(40)=300301, a(42)=366791 and a(46)=644869.

Cf. A002308, A097159.

A025046 a(n) = the least odd prime p such that there are exactly n consecutive quadratic remainders modulo p.

Original entry on oeis.org

3, 5, 19, 17, 67, 71, 131, 73, 277, 311, 827, 241, 1607, 2543, 3691, 1559, 6803, 5711, 14969, 1009, 43103, 10559, 52057, 2689, 90313, 162263, 127403, 18191, 209327, 31391, 607153, 8089, 1305511, 298483, 1694353, 33049, 3205777, 1523707

Offset: 2

David W. Wilson

nonn

The values -1,0,+1 are considered consecutive.

			a(5)=17 because -2,-1,0,+1,+2 are quadratic remainders, squares of 7,4,0,1,11.

Cf. A097159.

Edited by Don Reble, May 31 2007

A125607 Lesser of the smallest pair of consecutive positive reduced quadratic residues modulo p = prime(n) > 5.

Original entry on oeis.org

1, 3, 3, 1, 4, 1, 4, 1, 3, 1, 9, 1, 6, 3, 3, 9, 1, 1, 1, 3, 1, 1, 4, 1, 3, 3, 1, 1, 3, 1, 4, 4, 1, 3, 9, 1, 9, 3, 3, 1, 1, 6, 1, 4, 1, 3, 3, 1, 1, 1, 3, 1, 1, 4, 1, 3, 1, 6, 9, 6, 1, 1, 6, 4, 1, 3, 3, 1, 1, 1, 3, 4, 1, 4, 3, 1, 1, 3, 3, 1, 1, 1, 3, 1, 1, 4, 1, 3, 1, 1, 3, 4, 1, 4, 1, 6, 3, 9, 6, 3, 1, 4, 1, 3, 1

Offset: 4

Nick Hobson, Nov 30 2006

For all n, a(n) exists and equals 1, 3, 4, 6 or 9. Proof: a(4)=1 by inspection. For n > 4 (p > 7), if 2 is a quadratic residue of p, then a(n)=1; otherwise if 5 is a quadratic residue of p, then a(n)=4 or 3; otherwise 2*5=10 is a quadratic residue of p and (9, 10) are consecutive residues. However, a(n)=8 or 7 is impossible as 8 cannot be a quadratic residue (since 2 is not), leaving 9 and 6 as the other possible values.

The constant 0.133141413191633911131141331131441391... = sum(a(n)/10^(n-3)) is conjectured to be irrational.

			The quadratic residues of 13=prime(6) are 1, 3, 4, 9, 10 and 12. The least consecutive pair of residues is (3, 4); hence a(6)=3.

Nick Hobson, Table of n, a(n) for n = 4..1003
D. H. Lehmer and Emma Lehmer, On Runs of Residues, Proc. American Mathematical Society, Vol. 13, No. 1 (Feb., 1962), pp. 102-106.

Cf. A000445, A002307, A097159, A097160, A097161.

vector(108, m, p=prime(m+3); if(p%8==1||p%8==7, 1, if(p%12==1||p%12==11, 3, if(p%10==1||p%10==9, 4, if((p%24==1||p%24==5||p%24==19||p%24==23) && (p%28==1||p%28==3||p%28==9||p%28==19||p%28==25||p%28==27), 6, 9)))))

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

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A097161 Number of primes modulo which the largest number of consecutive quadratic residues is n.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

A025046 a(n) = the least odd prime p such that there are exactly n consecutive quadratic remainders modulo p.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A125607 Lesser of the smallest pair of consecutive positive reduced quadratic residues modulo p = prime(n) > 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI