cp's OEIS Frontend

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

%I A069003 #49 Feb 16 2025 08:32:45
%S A069003 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 A069003 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 A069003 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 A069003 Smallest integer d such that n^2 + d^2 is a prime number.
%C A069003 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 A069003 Conjecture: a(n) does not exceed 4*sqrt(n+1) for any positive integer n. - _Zhi-Wei Sun_, Apr 15 2013
%C A069003 Conjecture holds for the first 15*10^6 terms. - _Joerg Arndt_, Aug 19 2014
%C A069003 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 A069003 W. Sierpinski, Elementary Theory of Numbers, 2nd English edition, revised and enlarged by A. Schinzel, Elsevier, 1988.
%H A069003 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 A069003 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GaussianPrime.html">Gaussian Prime</a>.
%H A069003 Wikipedia, <a href="https://en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H">Schinzel's Hypothesis H</a>.
%e A069003 a(5)=2 because 2 is the smallest integer d such that 5^2+d^2 is a prime number.
%p A069003 f:= proc(n) local d;
%p A069003      for d from 1+(n mod 2) by 2 do
%p A069003        if isprime(n^2+d^2) then return d fi
%p A069003      od
%p A069003 end proc:
%p A069003 f(1):= 1:
%p A069003 map(f, [$1..1000]); # _Robert Israel_, Jul 06 2015
%t A069003 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 A069003 (PARI) a(n)=my(k);while(!isprime(n^2+k++^2),);k \\ _Charles R Greathouse IV_, Mar 20 2013
%Y A069003 Cf. A068486 (lists the prime numbers n^2 + d^2).
%Y A069003 Cf. A185636, A204065.
%Y A069003 Cf. A239388, A239389 (record values).
%Y A069003 Cf. A053000.
%K A069003 easy,nonn
%O A069003 1,3
%A A069003 _T. D. Noe_, Apr 02 2002