A069003 Smallest integer d such that n^2 + d^2 is a prime number.

1, 1, 2, 1, 2, 1, 2, 3, 4, 1, 4, 7, 2, 1, 2, 1, 2, 5, 6, 1, 4, 5, 8, 1, 4, 1, 2, 5, 4, 11, 4, 3, 2, 5, 2, 1, 2, 3, 10, 1, 4, 5, 8, 9, 2, 5, 2, 13, 4, 7, 4, 3, 10, 1, 4, 1, 2, 3, 6, 13, 10, 3, 32, 9, 2, 1, 2, 5, 10, 3, 6, 5, 2, 1, 4, 5, 10, 7, 4, 7, 4, 3, 18, 1, 2, 9, 2, 3, 4, 1, 4, 7, 8, 1, 2, 5, 2, 3, 4, 3

Offset: 1

Author

T. D. Noe, Apr 02 2002

Keywords

• easy
• nonn

Comments

With i being the imaginary unit, n + di is the smallest Gaussian prime with real part n and a positive imaginary part. Likewise for n - di. See A002145 for Gaussian primes with imaginary part 0. - Alonso del Arte, Feb 07 2011

Conjecture: a(n) does not exceed 4*sqrt(n+1) for any positive integer n. - Zhi-Wei Sun, Apr 15 2013

Conjecture holds for the first 15*10^6 terms. - Joerg Arndt, Aug 19 2014

Infinitely many d exist such that n^2 + d^2 is prime, under Schinzel's Hypothesis H; see Sierpinski (1988), p. 221. - Jonathan Sondow, Nov 09 2015

Examples

			a(5)=2 because 2 is the smallest integer d such that 5^2+d^2 is a prime number.
		

References

• W. Sierpinski, Elementary Theory of Numbers, 2nd English edition, revised and enlarged by A. Schinzel, Elsevier, 1988.

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
• Eric Weisstein's World of Mathematics, Gaussian Prime.
• Wikipedia, Schinzel's Hypothesis H.

Crossrefs

Cf. A068486 (lists the prime numbers n^2 + d^2).

Cf. A185636, A204065.

Cf. A239388, A239389 (record values).

Cf. A053000.

Programs

Maple

f:= proc(n) local d;
     for d from 1+(n mod 2) by 2 do
       if isprime(n^2+d^2) then return d fi
     od
end proc:
f(1):= 1:
map(f, [$1..1000]); # Robert Israel, Jul 06 2015

Mathematica

imP4P[n_] := Module[{k = 1}, While[Not[PrimeQ[n^2 + k^2]], k++]; k]; Table[imP4P[n], {n, 50}] (* Alonso del Arte, Feb 07 2011 *)

PARI

a(n)=my(k);while(!isprime(n^2+k++^2),);k \\ Charles R Greathouse IV, Mar 20 2013