|
%I M3608 #205 Apr 12 2024 09:21:21
%S 0,4,25,168,1229,9592,78498,664579,5761455,50847534,455052511,
%T 4118054813,37607912018,346065536839,3204941750802,29844570422669,
%U 279238341033925,2623557157654233,24739954287740860,234057667276344607,2220819602560918840,21127269486018731928,201467286689315906290
%N Number of primes < 10^n.
%C Number of primes with at most n digits; or pi(10^n).
%C Partial sums of A006879. - _Lekraj Beedassy_, Jun 25 2004
%C Also omega( (10^n)! ), where omega(x): number of distinct prime divisors of x. - _Cino Hilliard_, Jul 04 2007
%C This sequence also gives a good approximation for the sum of primes less than 10^(n/2). This is evident from the fact that the number of primes less than 10^2n closely approximates the sum of primes less than 10^n. See link on Sum of Primes for the derivation. - _Cino Hilliard_, Jun 08 2008
%C It appears that (10^n)/log((n+3)!) is a lower bound close to a(n), see A025201. - _Eric Desbiaux_, Jul 20 2010, edited by _M. F. Hasler_, Dec 03 2018
%D Richard Crandall and Carl B. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; p. 11.
%D Keith Devlin, Mathematics: The New Golden Age, new and revised edition. New York: Columbia University Press (1993): p. 6, Table 1.
%D Marcus du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; p. 48.
%D Calvin T. Long, Elementary Introduction to Number Theory. Prentice-Hall, Englewood Cliffs, NJ, 1987, p. 77.
%D Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 179.
%D H. Riesel, "Prime numbers and computer methods for factorization," Progress in Mathematics, Vol. 57, Birkhauser, Boston, 1985, page 38.
%D D. Shanks, Solved and Unsolved Problems in Number Theory. Chelsea, NY, 2nd edition, 1978, p. 15.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H David Baugh, <a href="/A006880/b006880.txt">Table of n, a(n) for n = 0..29</a> (terms n = 1..27 from Charles R Greathouse IV).
%H Chris K. Caldwell, <a href="http://www.utm.edu/research/primes/howmany.shtml">How Many Primes Are There?</a>
%H Chris K. Caldwell, <a href="http://www.utm.edu/research/primes/notes/md.html">Mark Deleglise's work</a>
%H Muhammed Hüsrev Cilasun, <a href="http://arxiv.org/abs/1412.3265">An Analytical Approach to Exponent-Restricted Multiple Counting Sequences</a>, arXiv preprint arXiv:1412.3265 [math.NT], 2014.
%H Muhammed Hüsrev Cilasun, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Cilasun/cila5.html">Generalized Multiple Counting Jacobsthal Sequences of Fermat Pseudoprimes</a>, Journal of Integer Sequences, Vol. 19, 2016, #16.2.3.
%H Jens Franke, Thorsten Kleinjung, Jan Büthe, and Alexander Jost, <a href="https://dx.doi.org/10.1090/mcom/3038">A practical analytic method for calculating pi(x)</a>, Math. Comp. 86 (2017), 2889-2909.
%H Xavier Gourdon, <a href="http://numbers.computation.free.fr/Constants/Primes/pixtable.html">a(22) found by pi(x) project</a>
%H Xavier Gourdon & Pascal Sebah, <a href="http://numbers.computation.free.fr/Constants/Primes/Pix/results.html">The pi(x) project : results and current computations</a>
%H Andrew Granville and Greg Martin, <a href="http://www.jstor.org/stable/27641834">Prime number races</a>, Amer. Math. Monthly, 113 (No. 1, 2006), 1-33.
%H Andrew Granville and Greg Martin, <a href="http://www.arXiv.org/abs/math.NT/0408319">Prime number races</a>, arXiv:math/0408319 [math.NT], 2004.
%H Cino Hilliard, <a href="http://docs.google.com/Doc?docid=dgpq9w4b_26dtrq634m&hl=en">Sum of primes</a> [unusable link]
%H Ronald K. Hoeflin, <a href="http://miyaguchi.4sigma.org/hoeflin/titan/titan.html">Titan Test</a>
%H D. S. Kluk and N. J. A. Sloane, <a href="/A002050/a002050_3.pdf">Correspondence, 1979</a>, [see p. 6 of the pdf]
%H J. C. Lagarias, V. S. Miller and A. M. Odlyzko, <a href="https://doi.org/10.1090/S0025-5718-1985-0777285-5">Computing pi(x): The Meissel-Lehmer method</a>, Math. Comp., 44 (1985), pp. 537-560.
%H J. C. Lagarias and Andrew M. Odlyzko, <a href="http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf">Computing pi(x): An analytic method</a>, J. Algorithms, 8 (1987), pp. 173-191.
%H Pieter Moree, Izabela Petrykiewicz, and Alisa Sedunova, <a href="https://arxiv.org/abs/1810.05244">A computational history of prime numbers and Riemann zeros</a>, arXiv:1810.05244 [math.NT], 2018. See Table 1 p. 6.
%H Tomás Oliveira e Silva, <a href="http://sweet.ua.pt/tos/primes.html">Tables of values of pi(x) and of pi2(x)</a>
%H Tomás Oliveira e Silva, <a href="http://sweet.ua.pt/tos/bib/5.4.pdf">Computing pi(x): the combinatorial method</a>, Revista do Detua, Vol. 4, N 6, March 2006.
%H David J. Platt, <a href="http://arxiv.org/abs/1203.5712">Computing pi(x) analytically</a>, arXiv:1203.5712 [math.NT], 2012-2013.
%H Vladimir Pletser, <a href="http://arxiv.org/abs/1307.4444">Conjecture on the value of Pi(10^26), the number of primes less than 10^26</a>, arXiv:1307.4444 [math.NT], 2013.
%H Vladimir Pletser, <a href="https://doi.org/10.20944/preprints202402.0545.v1">Global Generalized Mersenne Numbers: Definition, Decomposition, and Generalized Theorems</a>, Preprints.org, 2024. See p. 20.
%H Douglas B. Staple, <a href="http://arxiv.org/abs/1503.01839">The combinatorial algorithm for computing pi(x)</a>, arXiv:1503.01839 [math.NT], 2015.
%H M. R. Watkins, <a href="https://web.archive.org/web/20060611061124/http://www.maths.ex.ac.uk/~mwatkins/zeta/ss-a.htm">The distribution of prime numbers</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeCountingFunction.html">Prime Counting Function</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">Prime number theorem</a>
%H Robert G. Wilson, V, <a href="/A002982/a002982.pdf">Letter to N. J. A. Sloane, Jan. 1989</a>
%H <a href="/index/Pri#primepop">Index entries for sequences related to numbers of primes in various ranges</a>
%F a(n) = A000720(10^n). - _M. F. Hasler_, Dec 03 2018
%t Table[PrimePi[10^n], {n, 0, 14}] (* _Jean-François Alcover_, Nov 08 2016, corrected Sep 29 2020, a(14) being the maximum computable with certain implementations *)
%o (PARI) a(n)=primepi(10^n) \\ _Charles R Greathouse IV_, Nov 08 2011
%o (Haskell) a006880 = a000720 . (10 ^) -- _Reinhard Zumkeller_, Mar 17 2015
%Y Cf. A000720, A006879, A007053, A040014, A006988, A011557.
%K nonn,hard,nice
%O 0,2
%A _N. J. A. Sloane_ and _Simon Plouffe_
%E Lehmer gave the incorrect value 455052512 for the 10th term. More terms May 1996. _Jud McCranie_ points out that the 11th term is not 4188054813 but rather 4118054813.
%E a(22) from _Robert G. Wilson v_, Sep 04 2001
%E a(23) (see Gourdon and Sebah) has yet to be verified and the assumed error is +-1. - _Robert G. Wilson v_, Jul 10 2002 [The actual error was 14037804. - _N. J. A. Sloane_, Nov 28 2007]
%E a(23) corrected by _N. J. A. Sloane_ from the web page of Tomás Oliveira e Silva, Nov 28 2007
%E a(25) from J. Buethe, J. Franke, A. Jost, T. Kleinjung, Jun 01 2013, who said: "We have calculated pi(10^25) = 176846309399143769411680 unconditionally, using an analytic method based on Weil's explicit formula".
%E a(26) from _Douglas B. Staple_, Dec 02 2014
%E a(27) in the b-file from _David Baugh_ and Kim Walisch via _Charles R Greathouse IV_, Jun 01 2016
%E a(28) in the b-file from _David Baugh_ and Kim Walisch, Oct 26 2020
%E a(29) in the b-file from _David Baugh_ and Kim Walisch, Feb 28 2022
| 