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,2

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

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

Formula

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A088192, A176255.

Sequence in context: A023512 A322027 A088192 * A056062 A230517 A165003

Adjacent sequences: A218456 A218457 A218458 * A218460 A218461 A218462

Keyword

nonn,nice

Author

Alonso del Arte, Oct 29 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

Status

approved