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

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

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.

Example

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

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

Prog

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

Crossrefs

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

Cf. A185636, A204065.

Cf. A239388, A239389 (record values).

Cf. A053000.

Sequence in context: A177803 A274080 A074641 * A087855 A083409 A344779

Adjacent sequences: A069000 A069001 A069002 * A069004 A069005 A069006

Keyword

easy,nonn

Author

T. D. Noe, Apr 02 2002

Status

approved