%I #48 Oct 30 2023 08:15:29

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

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

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

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

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

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

%C Conjecture holds for the first 15*10^6 terms. - _Joerg Arndt_, Aug 19 2014

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

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

%H Zhi-Wei Sun, <a href="/A069003/b069003.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GaussianPrime.html">Gaussian Prime</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H">Schinzel's Hypothesis H</a>.

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

%p f:= proc(n) local d;

%p for d from 1+(n mod 2) by 2 do

%p if isprime(n^2+d^2) then return d fi

%p od

%p end proc:

%p f(1):= 1:

%p map(f, [$1..1000]); # _Robert Israel_, Jul 06 2015

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

%o (PARI) a(n)=my(k);while(!isprime(n^2+k++^2),);k \\ _Charles R Greathouse IV_, Mar 20 2013

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

%Y Cf. A185636, A204065.

%Y Cf. A239388, A239389 (record values).

%Y Cf. A053000.

%K easy,nonn

%O 1,3

%A _T. D. Noe_, Apr 02 2002