login
Number of primes of the form x^2 + 1 < 10^n.
18

%I #40 Aug 05 2020 19:12:08

%S 2,4,10,19,51,112,316,841,2378,6656,18822,54110,156081,456362,1339875,

%T 3954181,11726896,34900213,104248948,312357934,938457801,2826683630,

%U 8533327397,25814570672,78239402726,237542444180,722354138859,2199894223892

%N Number of primes of the form x^2 + 1 < 10^n.

%C It is conjectured that there are infinitely many primes of the form x^2 + 1 (and thus this sequence never becomes constant), but this has not been proved.

%C These primes can be found quickly using a sieve based on the fact that numbers of this form have at most one primitive prime factor (A005529). The sum of the reciprocals of these primes is 0.81459657... - _T. D. Noe_, Oct 14 2003

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 17.

%D P. Ribenboim, The Little Book of Big Primes. Springer-Verlag, 1991, p. 190.

%H C. K. Caldwell, <a href="http://www.utm.edu/~caldwell/preprints/Heuristics.pdf">An Amazing Prime Heuristic</a> A pdf file.

%H Jon Grantham, <a href="http://math.pseudoprime.com/2016/10/parallel-computation-of-primes-of-form.html">Parallel Computation of Primes of the form x^2+1</a>

%H Apoloniusz Tyszka, SÅ‚awomir Kurpaska, <a href="https://philarchive.org/archive/TYSDASv104">Open problems that concern computable sets X, subset of N, and cannot be formally stated as they refer to current knowledge about X</a>, (2020).

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

%H Marek Wolf, <a href="http://arXiv.org/abs/0803.1456">Search for primes of the form m^2+1</a>, arXiv:0803.1456 [math.NT], 2008-2010.

%e a(3) = 10 because the only primes or the form x^2 + 1 < 10^3 are the ten primes: 2, 5, 17, 37, 101, 197, 257, 401, 577, 677.

%t c = 1; k = 2; (* except for the initial prime 2, all X's must be odd. *) Do[ While[ k^2 + 1 < 10^n, If[ PrimeQ[k^2 + 1], c++ ]; k += 2]; Print[c], {n, 1, 20}]

%Y Cf. A005574, A002496, A083845, A083846, A083847, A083848, A083849, A214452, A214454, A214455.

%Y Cf. A005529 (primitive prime factors of the sequence k^2+1).

%K nonn

%O 1,1

%A _Harry J. Smith_, May 05 2003

%E Edited by _Robert G. Wilson v_, May 08 2003

%E More terms from _T. D. Noe_, Oct 14 2003

%E a(17)-a(22) from _Robert Gerbicz_, Apr 15 2009

%E a(23)-a(25) from Marek Wolf and Robert Gerbicz (code from Robert, computation done by Marek) _Robert Gerbicz_, Mar 13 2010

%E a(26)-a(28) from _Jon Grantham_, Jan 18 2017

%E a(28) corrected by _Jon Grantham_, Jan 30 2018