A088192 -id:A088192 - cp's OEIS frontend

A218459 a(n) is the smallest positive integer d such that prime(n) = x^2 + dy^2 has a solution (x,y) in integers.

1, 2, 1, 3, 2, 1, 1, 2, 7, 1, 3, 1, 1, 2, 11, 1, 2, 1, 2, 7, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 3, 2, 1, 2, 1, 3, 1, 2, 23, 1, 2, 1, 7, 1, 1, 3, 2, 3, 2, 1, 1, 7, 1, 2, 1, 7, 1, 3, 1, 1, 2, 1, 2, 11, 1, 1, 2, 1, 2, 1, 1, 7, 3, 1, 2, 22, 1, 1, 1, 1, 2, 1, 7, 1, 3, 2, 1, 1, 1, 3, 2, 19, 3, 2, 2

Offset: 1

Alonso del Arte, Oct 29 2012

a(n) = smallest positive integer d such that prime(n) is reducible in the ring Z[sqrt(-d)].
If prime(n) == 1 or 2 mod 4, then a(n) = 1. If prime(n) == 3 mod 8, then a(n) = 2. If prime(n) == 7 mod 24 then a(n) = 3.
If prime(n) == 23 mod 24, a(n) >= 7. In particular, the above conditions are if and only if. - Charles R Greathouse IV, Oct 31 2012
a(n) = 7 if and only if prime(n) is 11, 15, or 23 mod 28. - Charles R Greathouse IV, Nov 09 2012
It appears 75% of values are 1 or 2, with the vast majority of the rest prime, though many are duplicates. Conjecture: Odd composite values belong to A176255. - Bill McEachen, Sep 03 2023

			a(1) = 1 because the first prime is 2, which is 1^2 + 1^2.
a(2) = 2 because the second prime is 3, which is 1^2 + 2*1^2, but not of the form x^2 + y^2 for any integers x, y.
a(3) = 1 because the third prime is 5, which is 2^2 + 1*1^2.
a(4) = 3 because the third prime is 7, which is 2^2 + 3*1^2, but not of the form x^2 + y^2 or x^2 + 2y^2 for any integers x, y.

Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 68, Theorem 24.5; p. 74, Theorem 25.4.
David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, Section 9, "Ring class fields and p = x^2 + n y^2." - From N. J. A. Sloane, Dec 26 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Alonso del Arte, Diagram illustrating first six terms on the complex plane

Cf. A088192, A176255.

r[n_, d_] := Reduce[ Prime[n] == x^2 + d*y^2, {x, y}, Integers]; a[n_] := For[d = 1, True, d++, If[r[n, d] =!= False, Return[d] ] ]; Table[a[n], {n, 1, 95}] (* Jean-François Alcover, Apr 04 2013 *)

ndv(d, p)=(#bnfisintnorm(bnfinit(y^2+d), p))==0
forprime(p=2, 500, for(d=1, p, if(!ndv(d, p), print1(d, ", "); break))) \\ Georgi Guninski, Oct 27 2012

check(d,p)={
   if(kronecker(-d,p)<0 || #bnfisintnorm(bnfinit('x^2+d),p)==0, return(0));
   for(y=1,sqrtint(p\d),if(issquare(p-d*y^2),return(1)));
   0
};
do(p)={
   if(p%24<23,return(if(p%4<3,1,if(p%8==3,2,3))));
   if(kronecker(p,7)>0, return(7));
   if(check(11,p), return(11));
   for(d=19,p,
    if(issquarefree(d) && check(d,p), return(d))
   )
};
apply(do, primes(100)) \\ Charles R Greathouse IV, Oct 31 2012

A218459(n)={my(p=prime(n),d);while(d++,for(y=1,sqrtint((p-1)\d), issquare(p-d*y^2)&&return(d)))} \\ M. F. Hasler, May 05 2013

a(n) >= A088192(n). - Charles R Greathouse IV, Oct 31 2012

a(76) corrected by Charles R Greathouse IV, Nov 13 2012

Edited by N. J. A. Sloane, Dec 07 2012, Dec 26 2012

A248222 Maximal gap between quadratic residues mod n.

Original entry on oeis.org

1, 1, 2, 3, 3, 2, 3, 4, 3, 3, 4, 5, 5, 3, 5, 7, 4, 3, 5, 7, 6, 4, 5, 8, 3, 5, 3, 7, 4, 5, 5, 8, 6, 4, 5, 9, 5, 5, 6, 11, 6, 6, 6, 8, 6, 5, 5, 12, 4, 3, 6, 8, 7, 3, 8, 9, 7, 4, 6, 11, 7, 5, 9, 8, 9, 6, 7, 13, 7, 5, 7, 12, 5, 5, 7, 8, 11, 6, 7, 15, 3, 6, 8, 12, 13, 6, 11, 16, 7, 6

Offset: 1

David W. Wilson and M. F. Hasler, Oct 04 2014

nonn

"Maximal gap between squares mod n" would be a less ambiguous definition.
The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, even when n is a prime, 0 is not counted as a quadratic residue. In this entry, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n.
See A248376 for the variant with the additional restriction that the residue be coprime to the modulus. - M. F. Hasler, Oct 08 2014

			For n=7, the quadratic residues are all numbers congruent to 0, 1, 2, or 4 (mod 7), so the largest gap of 3 occurs for example between 4 = 2^2 (mod 7) and 7 = 0^2 (mod 7).
For n=16, the quadratic residues are the numbers congruent to 0, 1, 4 or 9 (mod 16), so the largest gap occurs between, e.g., 9 = 3^2 (mod 16) and 16 = 0^2 (mod 16).

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 45.
G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
Ivan Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers, New York: John Wiley, 2nd ed., 1966, p. 69. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Quadratic Residue
Wikipedia, Quadratic residue

Cf. A063987, A130290, A088190, A088191, A088192.

(DD(v)=vecextract(v,"^1")-vecextract(v,"^-1")); a(n)=vecmax(DD(select(f->issquare(Mod(f,n)),vector(n*2,i,i))))

Comments and references added by N. J. A. Sloane, Oct 04 2014

A248376 Maximal gap between quadratic residues mod n; here quadratic residues must be coprime to n.

Original entry on oeis.org

1, 2, 3, 4, 3, 6, 4, 8, 3, 8, 4, 12, 5, 8, 12, 8, 4, 6, 5, 12, 12, 8, 6, 24, 3, 8, 3, 16, 4, 18, 5, 8, 12, 8, 13, 12, 5, 10, 15, 32, 6, 24, 6, 16, 12, 12, 6, 24, 4, 8, 18, 20, 7, 6, 13, 32, 15, 10, 6, 48, 7, 10, 12, 8, 13, 24, 7, 16, 18, 20, 8, 24, 5, 10

Offset: 1

David W. Wilson and M. F. Hasler, Oct 05 2014

nonn

The definition of quadratic residue modulo a nonprime varies from author to author. Sometimes, quadratic residues are not required to be coprime to n, cf. A248222 for the corresponding variant of this sequence.

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 45.
G. B. Mathews, Theory of Numbers, 2nd edition. Chelsea, NY, p. 32. [Does not require gcd(q,n)=1.]
Ivan Niven and Herbert S. Zuckerman, An Introduction to the Theory of Numbers, New York: John Wiley, 2nd ed., 1966, p. 69. [Requires gcd(q,n)=1 for q to be a quadratic residue mod n.]
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 270. [Does not require gcd(q,n)=1.]

David W. Wilson, Table of n, a(n) for n = 1..10000
Eric W. Weisstein, MathWorld: Quadratic Residue
Wikipedia, Quadratic residue

Cf. A063987, A130290, A088190, A088191, A088192, A248222.

a(n)={L=m=1;for(i=2,n+1,gcd(i,n)>1&&next;issquare(Mod(i,n))||next;i-L>m&&m=i-L;L=i);m}

cp's OEIS Frontend

A218459 a(n) is the smallest positive integer d such that prime(n) = x^2 + dy^2 has a solution (x,y) in integers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A248222 Maximal gap between quadratic residues mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A248376 Maximal gap between quadratic residues mod n; here quadratic residues must be coprime to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI