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

%I #84 Oct 03 2023 10:09:15

%S 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,

%T 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,

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

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

%C a(n) = smallest positive integer d such that prime(n) is reducible in the ring Z[sqrt(-d)].

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

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

%C a(n) = 7 if and only if prime(n) is 11, 15, or 23 mod 28. - _Charles R Greathouse IV_, Nov 09 2012

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

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

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

%H Charles R Greathouse IV, <a href="/A218459/b218459.txt">Table of n, a(n) for n = 1..10000</a>

%H Alonso del Arte, <a href="/A218459/a218459_1.png">Diagram illustrating first six terms on the complex plane</a>

%F a(n) >= A088192(n). - _Charles R Greathouse IV_, Oct 31 2012

%e a(1) = 1 because the first prime is 2, which is 1^2 + 1^2.

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

%e a(3) = 1 because the third prime is 5, which is 2^2 + 1*1^2.

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

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

%o (PARI) ndv(d, p)=(#bnfisintnorm(bnfinit(y^2+d), p))==0

%o forprime(p=2, 500, for(d=1, p, if(!ndv(d, p), print1(d, ", "); break))) \\ _Georgi Guninski_, Oct 27 2012

%o (PARI) check(d,p)={

%o if(kronecker(-d,p)<0 || #bnfisintnorm(bnfinit('x^2+d),p)==0, return(0));

%o for(y=1,sqrtint(p\d),if(issquare(p-d*y^2),return(1)));

%o 0

%o };

%o do(p)={

%o if(p%24<23,return(if(p%4<3,1,if(p%8==3,2,3))));

%o if(kronecker(p,7)>0, return(7));

%o if(check(11,p), return(11));

%o for(d=19,p,

%o if(issquarefree(d) && check(d,p), return(d))

%o )

%o };

%o apply(do, primes(100)) \\ _Charles R Greathouse IV_, Oct 31 2012

%o (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

%Y Cf. A088192, A176255.

%K nonn,nice

%O 1,2

%A _Alonso del Arte_, Oct 29 2012

%E a(76) corrected by _Charles R Greathouse IV_, Nov 13 2012

%E Edited by _N. J. A. Sloane_, Dec 07 2012, Dec 26 2012