A005574 Numbers k such that k^2 + 1 is prime.

1, 2, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, 176, 180, 184, 204, 206, 210, 224, 230, 236, 240, 250, 256, 260, 264, 270, 280, 284, 300, 306, 314, 326, 340, 350, 384, 386, 396

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Hardy and Littlewood conjectured that the asymptotic number of elements in this sequence not exceeding n is approximately c*sqrt(n)/log(n) for some constant c. - Stefan Steinerberger, Apr 06 2006

Also, nonnegative integers such that a(n)+i is a Gaussian prime. - Maciej Ireneusz Wilczynski, May 30 2011

Apparently Goldbach conjectured that any a > 1 from this sequence can be written as a=b+c where b and c are in this sequence (Lemmermeyer link below). - Jeppe Stig Nielsen, Oct 14 2015

No term > 2 can be both in this sequence and in A001105 because of the Aurifeuillean factorization (2*k^2)^2 + 1 = (2*k^2 - 2*k + 1) * (2*k^2 + 2*k + 1). - Jeppe Stig Nielsen, Aug 04 2019

References

• Harvey Dubner, "Generalized Fermat primes", J. Recreational Math., 18 (1985): 279-280.
• R. K. Guy, "Unsolved Problems in Number Theory", 3rd edition, A2.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, p. 15, Thm. 17.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• H. Dubner, Generalized Fermat primes, J. Recreational Math. 18.4 (1985-1986), 279. (Annotated scanned copy)
• F. Ellermann, Primes of the form (m^2)+1 up to 10^6.
• L. Euler, Lettre CXLIX (to Goldbach), 1752.
• L. Euler, De numeris primis valde magnis, Novi Commentarii academiae scientiarum Petropolitanae 9 (1764), pp. 99-153. See pp. 123-125.
• R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy).
• F. Lemmermeyer, Primes of the form a^2+1, Math Overflow question (2010).
• Eric Weisstein's World of Mathematics, Landau's Problems.
• Eric Weisstein's World of Mathematics, Power.
• Eric Weisstein's World of Mathematics, Near-Square Prime.
• Marek Wolf, Search for primes of the form m^2+1, arXiv:0803.1456 [math.NT], 2008-2010.

Crossrefs

Cf. A002522, A001912, A002496, A062325, A090693, A000068, A006314, A006313, A006315, A006316, A056994, A056995, A057465, A057002, A088361, A088362, A226528, A226529, A226530, A251597, A253854, A244150, A243959, A321323.

Other sequences of the type "Numbers k such that k^2 + i is prime": this sequence (i=1), A067201 (i=2), A049422 (i=3), A007591 (i=4), A078402 (i=5), A114269 (i=6), A114270 (i=7), A114271 (i=8), A114272 (i=9), A114273 (i=10), A114274 (i=11), A114275 (i=12).

Cf. A010051, A259645, A295405 (characteristic function).

Programs

Haskell

a005574 n = a005574_list !! (n-1)
a005574_list = filter ((== 1) . a010051' . (+ 1) . (^ 2)) [0..]
-- Reinhard Zumkeller, Jul 03 2015

Magma

[n: n in [0..400] | IsPrime(n^2+1)]; // Vincenzo Librandi, Nov 18 2010

Mathematica

Select[Range[350], PrimeQ[ #^2 + 1] &] (* Stefan Steinerberger, Apr 06 2006 *)
Join[{1},2Flatten[Position[PrimeQ[Table[x^2+1,{x,2,1000,2}]],True]]]  (* Fred Patrick Doty, Aug 18 2017 *)

PARI

isA005574(n) = isprime(n^2+1) \\ Michael B. Porter, Mar 20 2010

PARI

for(n=1, 1e3, if(isprime(n^2 + 1), print1(n, ", "))) \\ Altug Alkan, Oct 14 2015

Python

from sympy import isprime; [print(n, end = ', ') for n in range(1, 400) if isprime(n*n+1)] # Ya-Ping Lu, Apr 23 2025

Formula

a(n) = A090693(n) - 1.

a(n) = 2*A001912(n-1) for n > 1. - Jeppe Stig Nielsen, Aug 04 2019