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

Author

Alonso del Arte, Oct 29 2012

Keywords

• nonn
• nice

Comments

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

Examples

			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.
		

References

• 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

Links

• 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

Crossrefs

Cf. A088192, A176255.

Programs

Mathematica

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 *)

PARI

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

PARI

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

PARI

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

Formula

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

Extensions

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

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