|
%I M0652 N0241 #1217 Apr 22 2024 04:43:53
%S 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
%T 97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,
%U 181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271
%N The prime numbers.
%C See A065091 for comments, formulas etc. concerning only odd primes. For all information concerning prime powers, see A000961. For contributions concerning "almost primes" see A002808.
%C A number p is prime if (and only if) it is greater than 1 and has no positive divisors except 1 and p.
%C A natural number is prime if and only if it has exactly two (positive) divisors.
%C A prime has exactly one proper positive divisor, 1.
%C The paper by Kaoru Motose starts as follows: "Let q be a prime divisor of a Mersenne number 2^p-1 where p is prime. Then p is the order of 2 (mod q). Thus p is a divisor of q - 1 and q > p. This shows that there exist infinitely many prime numbers." - Pieter Moree, Oct 14 2004
%C 1 is not a prime, for if the primes included 1, then the factorization of a natural number n into a product of primes would not be unique, since n = n*1.
%C Prime(n) and pi(n) are inverse functions: A000720(a(n)) = n and a(n) is the least number m such that a(A000720(m)) = a(n). a(A000720(n)) = n if (and only if) n is prime.
%C Second sequence ever computed by electronic computer, on EDSAC, May 09 1949 (see Renwick link). - _Russ Cox_, Apr 20 2006
%C Every prime p > 3 is a linear combination of previous primes prime(n) with nonzero coefficients c(n) and |c(n)| < prime(n). - _Amarnath Murthy_, _Franklin T. Adams-Watters_ and _Joshua Zucker_, May 17 2006; clarified by _Chayim Lowen_, Jul 17 2015
%C The Greek transliteration of 'Prime Number' is 'Protos Arithmos'. - _Daniel Forgues_, May 08 2009 [Edited by _Petros Hadjicostas_, Nov 18 2019]
%C A number n is prime if and only if it is different from zero and different from a unit and each multiple of n decomposes into factors such that n divides at least one of the factors. This applies equally to the integers (where a prime has exactly four divisors (the definition of divisors is relaxed such that they can be negative)) and the positive integers (where a prime has exactly two distinct divisors). - _Peter Luschny_, Oct 09 2012
%C Motivated by his conjecture on representations of integers by alternating sums of consecutive primes, for any positive integer n, Zhi-Wei Sun conjectured that the polynomial P_n(x) = Sum_{k=0..n} a(k+1)*x^k is irreducible over the field of rational numbers with the Galois group S_n, and moreover P_n(x) is irreducible mod a(m) for some m <= n(n+1)/2. It seems that no known criterion on irreduciblity of polynomials implies this conjecture. - _Zhi-Wei Sun_, Mar 23 2013
%C Questions on a(2n) and Ramanujan primes are in A233739. - _Jonathan Sondow_, Dec 16 2013
%C From _Hieronymus Fischer_, Apr 02 2014: (Start)
%C Natural numbers such that there is exactly one base b such that the base-b alternate digital sum is 0 (see A239707).
%C Equivalently: Numbers p > 1 such that b = p-1 is the only base >= 1 for which the base-b alternate digital sum is 0.
%C Equivalently: Numbers p > 1 such that the base-b alternate digital sum is <> 0 for all bases 1 <= b < p-1. (End)
%C An integer n > 1 is a prime if and only if it is not the sum of positive integers in arithmetic progression with common difference 2. - _Jean-Christophe Hervé_, Jun 01 2014
%C Conjecture: Numbers having prime factors <= prime(n+1) are {k|k^f(n) mod primorial(n)=1}, where f(n) = lcm(prime(i)-1, i=1..n) = A058254(n) and primorial(n) = A002110(n). For example, numbers with no prime divisor <= prime(7) = 17 are {k|k^60 mod 30030=1}. - _Gary Detlefs_, Jun 07 2014
%C Cramer conjecture prime(n+1) - prime(n) < C log^2 prime(n) is equivalent to the inequality (log prime(n+1)/log prime(n))^n < e^C, as n tend to infinity, where C is an absolute constant. - _Thomas Ordowski_, Oct 06 2014
%C I conjecture that for any positive rational number r there are finitely many primes q_1,...,q_k such that r = Sum_{j=1..k} 1/(q_j-1). For example, 2 = 1/(2-1) + 1/(3-1) + 1/(5-1) + 1/(7-1) + 1/(13-1) with 2, 3, 5, 7 and 13 all prime, 1/7 = 1/(13-1) + 1/(29-1) + 1/(43-1) with 13, 29 and 43 all prime, and 5/7 = 1/(3-1) + 1/(7-1) + 1/(31-1) + 1/(71-1) with 3, 7, 31 and 71 all prime. - _Zhi-Wei Sun_, Sep 09 2015
%C I also conjecture that for any positive rational number r there are finitely many primes p_1,...,p_k such that r = Sum_{j=1..k} 1/(p_j+1). For example, 1 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(11+1) + 1/(23+1) with 2, 3, 5, 7, 11 and 23 all prime, and 10/11 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(43+1) + 1/(131+1) + 1/(263+1) with 2, 3, 5, 7, 43, 131 and 263 all prime. - _Zhi-Wei Sun_, Sep 13 2015
%C Numbers k such that ((k-2)!!)^2 == +-1 (mod k). - _Thomas Ordowski_, Aug 27 2016
%C Does not satisfy Benford's law [Diaconis, 1977; Cohen-Katz, 1984; Berger-Hill, 2017]. - _N. J. A. Sloane_, Feb 07 2017
%C Prime numbers are the integer roots of 1 - sin(Pi*Gamma(s)/s)/sin(Pi/s). - _Peter Luschny_, Feb 23 2018
%C Conjecture: log log a(n+1) - log log a(n) < 1/n. - _Thomas Ordowski_, Feb 17 2023
%D M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.
%D T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
%D E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I, Chaps. 8, 9.
%D D. M. Bressoud, Factorization and Primality Testing, Springer-Verlag NY 1989.
%D M. Cipolla, "La determinazione asintotica dell'n-mo numero primo.", Rend. d. R. Acc. di sc. fis. e mat. di Napoli, s. 3, VIII (1902), pp. 132-166.
%D R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 1.
%D Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing the World", Cambridge 2016.
%D J.-P. Delahaye, Merveilleux nombres premiers, Pour la Science-Belin Paris, 2000.
%D J.-P. Delahaye, Savoir si un nombre est premier: facile, Pour La Science, 303(1) 2003, pp. 98-102.
%D Diaconis, Persi, The distribution of leading digits and uniform distribution mod 1, Ann. Probability, 5, 1977, 72--81,
%D M. Dietzfelbinger, Primality Testing in Polynomial Time, Springer NY 2004.
%D M. du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; see p. 5.
%D J. Elie, "L'algorithme AKS", in 'Quadrature', No. 60, pp. 22-32, 2006 EDP-sciences, Les Ulis (France);
%D W. & F. Ellison, Prime Numbers, Hermann Paris 1985
%D T. Estermann, Introduction to Modern Prime Number Theory, Camb. Univ. Press, 1969.
%D J. M. Gandhi, Formulae for the nth prime. Proc. Washington State Univ. Conf. on Number Theory, 96-106. Wash. St. Univ., Pullman, Wash., 1971.
%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.
%D Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. (260-264).
%D H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035, cf. http://www.ams.org/mathscinet-getitem?mr=1336709
%D M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972.
%D D. S. Jandu, Prime Numbers And Factorization, Infinite Bandwidth Publishing, N. Hollywood CA 2007.
%D E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea, NY, 1974.
%D D. H. Lehmer, The sieve problem for all-purpose computers. Math. Tables and Other Aids to Computation, Math. Tables and Other Aids to Computation, 7, (1953). 6-14. Math. Rev. 14:691e
%D D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.
%D W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, Chap. 6.
%D H. Lifchitz, Table des nombres premiers de 0 à 20 millions (Tomes I & II), Albert Blanchard, Paris 1971.
%D R. F. Lukes, C. D. Patterson and H. C. Williams, Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), no. 1, 113-139. Math. Rev. 96m:11082, cf http://www.ams.org/mathscinet-getitem?mr=96m:11082
%D P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag NY 1995.
%D P. Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004.
%D H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser Boston, Cambridge MA 1994.
%D B. Rittaud, "31415879. Ce nombre est-il premier?" ['Is this number prime?'], La Recherche, Vol. 361, pp. 70-73, Feb 15 2003, Paris.
%D D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, Chap. 1.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D D. Wells, Prime Numbers: The Most Mysterious Figures In Math, J. Wiley NY 2005.
%D H. C. Williams and Jeffrey Shallit, Factoring integers before computers. Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), 481-531, Proc. Sympos. Appl. Math., 48, AMS, Providence, RI, 1994. Math. Rev. 95m:11143
%H N. J. A. Sloane, <a href="/A000040/b000040.txt">Table of n, prime(n) for n = 1..10000</a>
%H N. J. A. Sloane, <a href="/A000040/a000040.txt">Table of n, prime(n) for n = 1..100000</a>
%H M. Agrawal, N. Kayal & N. Saxena, <a href="http://annals.math.princeton.edu/2004/160-2/p12">PRIMES is in P</a>, Annals of Maths., 160:2 (2004), pp. 781-793. [<a href="https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">alternative link</a>]
%H M. Agrawal, <a href="http://www.cse.iitk.ac.in/users/manindra/presentations/GodelTalk.pdf ">A Short History of "PRIMES is in P"</a>
%H P. Alfeld, <a href="http://www.math.utah.edu/~alfeld/math/prime.html">Notes and Literature on Prime Numbers</a>
%H J. W. Andrushkiw, R. I. Andrushkiw and C. E. Corzatt, <a href="http://www.jstor.org/stable/2689456">Representations of Positive Integers as Sums of Arithmetic Progressions</a>, Mathematics Magazine, Vol. 49, No. 5 (Nov., 1976), pp. 245-248.
%H Anonymous, <a href="http://www.mathematical.com/primelist1to100kk.html">Prime Number Master Index (for primes up to 2*10^7)</a>
%H Anonymous, <a href="http://everything2.net/index.pl?node_id=74889&displaytype=printable&lastnode_id=74889">prime number</a>
%H Christian Axler, <a href="https://arxiv.org/abs/1706.03651">New estimates for the n-th prime number</a>, arXiv:1706.03651 [math.NT], 2017.
%H P. T. Bateman & H. G. Diamond, <a href="http://www.jstor.org/stable/2974443">A Hundred Years of Prime Numbers</a>, Amer. Math. Month., Vol. 103 (9), Nov. 1996, pp. 729-741.
%H A. Berger and T. P. Hill, <a href="http://www.ams.org/publications/journals/notices/201702/rnoti-p132.pdf">What is Benford's Law?</a>, Notices, Amer. Math. Soc., 64: 2 (2017), 132-134.
%H E. R. Berlekamp, <a href="/A257113/a257113.pdf">A contribution to mathematical psychometrics</a>, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
%H D. J. Bernstein, <a href="http://cr.yp.to/papers/aks.pdf">Proving Primality After Agrawal-Kayal-Saxena</a>
%H D. J. Bernstein, <a href="http://cr.yp.to/primetests.html">Distinguishing prime numbers from composite numbers</a>
%H P. Berrizbeitia, <a href="http://arXiv.org/abs/math.NT/0211334">Sharpening "Primes is in P" for a large family of numbers</a>, arXiv:math/0211334 [math.NT], 2002.
%H A. Booker, <a href="https://t5k.org/nthprime">The Nth Prime Page</a>
%H F. Bornemann, <a href="http://www.ams.org/notices/200305/fea-bornemann.pdf">PRIMES Is in P: A Breakthrough for "Everyman"</a>, Notices, Amer. Math. Soc., 50: 5 (2003), 545-552.
%H A. Bowyer, <a href="http://www.bath.ac.uk/~ensab/Primes">Formulae for Primes</a> [broken link ?]
%H B. M. Bredikhin, <a href="http://eom.springer.de/P/p074530.htm">Prime number</a>
%H R. P. Brent, <a href="http://wwwmaths.anu.edu.au/~brent/pub/pub120.html">Primality testing and integer factorization</a>
%H J. Britton, <a href="http://britton.disted.camosun.bc.ca/jbprimelist.htm">Prime Number List</a> [Dead link]
%H D. Butler, <a href="https://web.archive.org/web/20191118082053/http://www.tsm-resources.com/alists/prim.html">The first 2000 Prime Numbers</a>
%H C. K. Caldwell, <a href="https://t5k.org/">The Prime Pages</a>: <a href="https://t5k.org/glossary/page.php?sort=TablesOfPrimes">Tables of primes</a>; <a href="https://t5k.org/lists/small/">Lists of small primes</a> (from the first 1000 primes to all 50,000,000 primes up to 982,451,653.)
%H C. K. Caldwell, <a href="https://t5k.org/curios/includes/file.php?file=primetest.html">A Primality Test</a>
%H C. K. Caldwell and Y. Xiong, <a href="http://arxiv.org/abs/1209.2007">What is the smallest prime?</a>, J. Integer Seq. 15 (2012), no. 9, Article 12.9.7 and arXiv:1209.2007 [math.HO], 2012.
%H Chris K. Caldwell, Angela Reddick, Yeng Xiong and Wilfrid Keller, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html">The History of the Primality of One: A Selection of Sources</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.
%H Ernesto Cesàro, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k30752/f848.item">Sur une formule empirique de M. Pervouchine</a>, Comptes rendus hebdomadaires des séances de l'Académie des sciences (in French), 119 (1894), 848-849.
%H M. Chamness, <a href="http://www.alumni.caltech.edu/~chamness/prime.html">Prime number generator (Applet)</a>
%H Daniel I. A. Cohen and Talbot M. Katz, <a href="https://doi.org/10.1016/0022-314X(84)90061-1">Prime numbers and the first digit phenomenon</a>, J. Number Theory 18 (1984), 261-268.
%H P. Cox, <a href="http://members.cox.net/mathmistakes/primes.htm">Primes is in P</a>
%H P. J. Davis & R. Hersh, The Mathematical Experience, <a href="http://www.fortunecity.com/emachines/e11/86/mathex5.html">The Prime Number Theorem</a>
%H J.-M. De Koninck, <a href="https://www.jeanmariedekoninck.mat.ulaval.ca/fileadmin/jmdk/Documents/Conferences/NP_college_stanislas_2013.pdf">Les nombres premiers: mystères et consolation</a>
%H J.-M. De Koninck, <a href="https://docplayer.fr/69889747-Nombres-premiers-mysteres-et-enjeux-jean-marie-de-koninck.html">Nombres premiers: mystères et enjeux</a>
%H J.-P. Delahaye, <a href="http://www.cnrs.fr/Cnrspresse/math2000/html/math10.htm">Formules et nombres premiers</a>
%H U. Dudley, <a href="http://www.jstor.org/stable/2690261">Formulas for primes</a>, Math. Mag., 56 (1983), 17-22.
%H Pierre Dusart, <a href="http://www.unilim.fr/laco/theses/1998/T1998_01.pdf">Autour de la fonction qui compte le nombre de nombres premiers</a>, Thèse, Université de Limoges, France, (1998).
%H Pierre Dusart, <a href="http://dx.doi.org/10.1090/S0025-5718-99-01037-6">The k-th prime is greater than k(ln k + ln ln k-1) for k>=2</a>, Mathematics of Computation 68: (1999), 411-415.
%H J. Elie, <a href="http://www.trigofacile.com/maths/curiosite/primarite/aks/pdf/algorithme-aks.pdf">L'algorithme AKS ou Les nombres premiers sont de classe P</a>
%H Seymour B. Elk, <a href="https://doi.org/10.1021/ci00020a031">Prime Number Assignment to a Hexagonal Tessellation of a Plane That Generates Canonical Names for Peri-Condensed Polybenzenes</a>, J. Chem. Inf. Comput. Sci., vol. 34 (1994), pp. 942-946.
%H David Eppstein, <a href="https://arxiv.org/abs/1804.07396">Making Change in 2048</a>, arXiv:1804.07396 [cs.DM], 2018.
%H Leonhard Euler, <a href="https://arxiv.org/abs/math/0501118">Observations on a theorem of Fermat and others on looking at prime numbers</a>, arXiv:math/0501118 [math.HO], 2005-2008.
%H W. Fendt, <a href="https://www.walter-fendt.de/html5/men/primenumbers_en.htm">Table of Primes from 1 to 1000000000000</a>
%H P. Flajolet, S. Gerhold and B. Salvy, <a href="http://arxiv.org/abs/math/0501379">On the non-holonomic character of logarithms, powers and the n-th prime function</a>, arXiv:math/0501379 [math.CO], 2005.
%H J. Flamant, <a href="http://jocelyn.smoofy.net/np/cache/index.html">Primes up to one million</a>
%H K. Ford, Expositions of the <a href="http://www.math.uiuc.edu/~ford">PRIMES is in P</a> theorem.
%H H. Furstenberg, <a href="https://www.jstor.org/stable/2307043">On the Infinitude of Primes</a>, The American Mathematical Monthly, Vol. 62, No. 5 (May, 1955), p. 353 (1 page).
%H L. & Y. Gallot, <a href="http://yves.gallot.pagesperso-orange.fr/primes/chrrcds.html">The Chronology of Prime Number Records</a>
%H P. Garrett, <a href="http://www.math.umn.edu/~garrett/crypto/overheads01.pdf">Big Primes, Factoring Big Integers</a>
%H P. Garrett, <a href="http://www.math.umn.edu/~garrett/js/naive_prim_test.html">Naive Primality Test</a>
%H P. Garrett, <a href="http://www.math.umn.edu/~garrett/js/list_pr.html">Listing Primes</a>
%H N. Gast, <a href="http://web.archive.org/web/20070412005510/http://www.eleves.ens.fr/home/gast/misc/GastCrypto.pdf">PRIMES is in P: Manindra Agrawal, Neeraj Kayal and Nitin Saxena</a> (in French)
%H D. A. Goldston, S. W. Graham, J. Pintz and C. Y. Yildirim, <a href="http://arXiv.org/abs/math.NT/0506067">Small gaps between primes and almost primes</a>, arXiv:math/0506067 [math.NT], 2005.
%H S. W. Golomb, <a href="https://www.jstor.org/stable/2319567">A Direct Interpretation of Gandhi's Formula</a>, Mathematics Magazine, Vol. 81, No. 7 (Aug. - Sep., 1974), pp. 752-754.
%H A. Granville, <a href="http://www.ams.org/bull/2005-42-01/S0273-0979-04-01037-7/home.html">It is easy to determine whether a given integer is prime</a> [<a href="http://math.stanford.edu/~brubaker/granville.pdf">alternate link</a>]
%H P. Hartmann, <a href="http://www.beweise.mathematic.de/">Prime number proofs</a> (in German)
%H Haskell Wiki, <a href="http://www.haskell.org/haskellwiki/Prime_numbers">Prime Numbers</a>
%H ICON Project, <a href="http://www.cs.arizona.edu/icon/oddsends/primes.htm">List of first 50000 primes grouped within ten columns</a>
%H James P. Jones, Daihachiro Sato, Hideo Wada and Douglas Wiens, <a href="https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/JonesSatoWadaWiens.pdf">Diophantine representation of the set of prime numbers</a>, The American Mathematical Monthly 83, no. 6 (1976): 449-464. DOI: 10.2307/2318339.
%H N. Kayal and N. Saxena, <a href="http://www.ias.ac.in/resonance/Nov2002/pdf/Nov2002ResearchNews.pdf">A polynomial time algorithm to test if a number is prime or not</a>, Resonance 11-2002.
%H E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, <a href="http://name.umdl.umich.edu/ABV2766.0001.001">vol. 1</a> and <a href="http://name.umdl.umich.edu/ABV2766.0002.001">vol. 2</a>, Leipzig, Berlin, B. G. Teubner, 1909.
%H W. Liang & H. Yan, <a href="http://arxiv.org/abs/math/0603450">Pseudo Random test of prime numbers</a>, arXiv:math/0603450 [math.NT], 2006.
%H J. Malkevitch, <a href="http://www.ams.org/featurecolumn/archive/primes1.html">Primes</a>
%H Mathworld Headline News, <a href="http://mathworld.wolfram.com/news/2002-08-07/primetest/">Primality Testing is Easy</a>
%H K. Matthews, <a href="http://www.numbertheory.org/php/prime_generator.html">Generating prime numbers</a>
%H Y. Motohashi, <a href="http://arXiv.org/abs/math.HO/0512143">Prime numbers-your gems</a>, arXiv:math/0512143 [math.HO], 2005.
%H Kaoru Motose, <a href="http://www.math.okayama-u.ac.jp/mjou/mjou1-46/mjou_pdf/mjou_37/mjou_37_027.pdf">On values of cyclotomic polynomials. II</a>, Math. J. Okayama Univ. 37 (1995), 27-36.
%H J. Moyer, <a href="http://www.rsok.com/~jrm/printprimes.html">Some Prime Numbers</a>
%H C. W. Neville, <a href="http://arXiv.org/abs/math.NT/0210282">New Results on Primes from an Old Proof of Euler's</a>, arXiv:math/0210282 [math.NT], 2002-2003.
%H L. C. Noll, <a href="http://www.isthe.com/chongo/tech/math/prime/">Prime numbers, Mersenne Primes, Perfect Numbers, etc.</a>
%H M. A. Nyblom and C. Evans, <a href="http://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p149.pdf">On the enumeration of partitions with summands in arithmetic progression</a>, Australasian Journal of Combinatorics, Vol. 28 (2003), pp. 149-159.
%H J. J. O'Connor & E. F. Robertson, <a href="http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Prime_numbers.html">Prime Numbers</a>
%H M. E. O'Neill, <a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">The Genuine Sieve of Eratosthenes</a>, J. of Functional Programming, Vol 19 Issue 1, Jan 2009, p. 95ff, CUP NY
%H M. Ogihara & S. Radziszowski, <a href="http://www.cs.rit.edu/~spr/PUBL/primes.pdf">Agrawal-Kayal-Saxena Algorithm for Testing Primality in Polynomial Time</a>
%H P. Papaphilippou, <a href="http://www.philippos.info/unit_c/primeg/">Plotter of prime numbers frequency graph (flash object)</a> [From Philippos Papaphilippou (philippos(AT)safe-mail.net), Jun 02 2010]
%H J. M. Parganin, <a href="http://noe-education.org/D11102.php">Primes less than 50000</a>
%H Matthew Parker, <a href="https://oeis.org/A000040/a000040_1B.7z">The first billion primes (7-Zip compressed file)</a> [a large file]
%H Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/07-Sequence%20Pictures/mathgames_12_08_03.html">Sequence Pictures</a>, Math Games column, Dec 08 2003. [<a href="/A000043/a000043_2.pdf">Cached copy, with permission (pdf only)</a>]
%H I. Peterson, <a href="http://www.fortunecity.com/emachines/e11/86/tourist2b.html">Prime Pursuits</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/4.jpg">Illustration of initial terms</a>
%H Omar E. Pol, <a href="http://www.polprimos.com">Sobre el patrón de los números primos</a>, and from Jason Davies, <a href="https://www.jasondavies.com/primos">An interactive companion (for primes 2..997)</a>
%H Popular Computing (Calabasas, CA), <a href="/A003309/a003309.pdf">Sieves: Problem 43</a>, Vol. 2 (No. 13, Apr 1974), pp. 6-7. [Annotated and scanned copy]
%H Primefan, <a href="http://primefan.tripod.com/500Primes1.html">The First 500 Prime Numbers</a> and <a href="http://primefan.tripod.com/PrimeLister.html">Script to Calculate Prime Numbers</a>.
%H Project Gutenberg Etext, <a href="http://www.gutenberg.org/etext/65">First 100,000 Prime Numbers</a>
%H C. D. Pruitt, <a href="http://www.mathematical.com/mathprimegen.html">Formulae for Generating All Prime Numbers</a>
%H R. Ramachandran, Frontline 19 (17) 08-2000, <a href="http://www.flonnet.com/fl1917/19171290.htm">A Prime Solution</a>
%H W. S. Renwick, <a href="http://www.cl.cam.ac.uk/Relics/elog.html">EDSAC log</a>.
%H F. Richman, <a href="http://math.fau.edu/Richman/primes.htm">Generating primes by the sieve of Eratosthenes</a>
%H Barkley Rosser, <a href="http://www.jstor.org/stable/2371291">Explicit Bounds for Some Functions of Prime Numbers</a>, American Journal of Mathematics 63 (1941) 211-232.
%H J. Barkley Rosser and Lowell Schoenfeld, <a href="http://projecteuclid.org/euclid.ijm/1255631807"> Approximate formulas for some functions of prime numbers</a>, Illinois J. Math. Volume 6, Issue 1 (1962), 64-94.
%H S. M. Ruiz and J. Sondow, <a href="http://arXiv.org/abs/math.NT/0210312">Formulas for pi(n) and the n-th prime</a>, arXiv:math/0210312 [math.NT], 2002-2014.
%H S. O. S. Math, <a href="http://www.sosmath.com/tables/prime/prime.html">First 1000 Prime Numbers</a>
%H A. Schulman, <a href="http://www.sonic.net/~undoc/java/PrimeCalc.html">Prime Number Calculator</a>
%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 5.
%H M. Slone, PlanetMath.Org, <a href="http://planetmath.org/encyclopedia/FirstThousandPositivePrimeNumbers.html">First thousand positive prime numbers</a>
%H A. Stiglic, <a href="http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html">The PRIMES is in P little FAQ</a>
%H Zhi-Wei Sun, <a href="http://dx.doi.org/10.1016/j.jnt.2013.02.003">On functions taking only prime values</a>, J. Number Theory, 133 (2013), no. 8, 2794-2812.
%H Zhi-Wei Sun, <a href="http://maths.nju.edu.cn/~zwsun/UnitFraction.pdf">A conjecture on unit fractions involving primes</a>, Preprint 2015.
%H J. Teitelbaum, <a href="http://www.ams.org/bull/2002-39-03/S0273-0979-02-00947-3/S0273-0979-02-00947-3.pdf">Review of "Prime numbers:A computational perspective" by R. Crandall & C. Pomerance</a>
%H J. Thonnard, <a href="http://www.proftnj.com/calcprem.htm">Les nombres premiers(Primality check; Closest next prime; Factorizer)</a>
%H J. Tramu, <a href="http://www.echolalie.org/gbgraph/gb/index.htm">Movie of primes scrolling</a>
%H A. Turpel, <a href="http://www2.vo.lu/homepages/armand/index.html">Aesthetics of the Prime Sequence</a> [broken link ?]
%H S. Wagon, <a href="http://www.americanscientist.org/bookshelf/pub/prime-time">Prime Time: Review of "Prime Numbers:A Computational Perspective" by R. Crandall & C. Pomerance</a>
%H M. R. Watkins, <a href="http://www.maths.ex.ac.uk/~mwatkins/zeta/unusual.htm">unusual and physical methods for finding prime numbers</a>
%H S. Wedeniwski, <a href="http://w210.Ub.uni-tuebingen.de/dbt/volltexte/2001/420/pdf/dissertation.pdf">Primality Tests on Commutator Curves</a>
%H E. Wegrzynowski, <a href="https://web.archive.org/web/20160413222527/http://www.lifl.fr/~wegrzyno/FormulPrem/FormulesPremiers23.html">Les formules simples qui donnent des nombres premiers en grande quantité</a> (in French).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html">Prime-Generating Polynomial</a>, <a href="http://mathworld.wolfram.com/PrimeNumber.html">Prime Number</a>, and <a href="http://mathworld.wolfram.com/PrimeSpiral.html">Prime Spiral</a>.
%H Wikipedia, <a href="https://www.wikipedia.org/wiki/Prime_number">Prime number</a> and <a href="https://www.wikipedia.org/wiki/Prime_number_theorem">Prime number theorem</a>.
%H G. Xiao, Primes server, <a href="http://wims.unice.fr/~wims/en_tool~number~primes.html">Sequential Batches Primes Listing (up to orders not exceeding 10^308)</a>
%H G. Xiao, Numerical Calculator, <a href="http://wims.unice.fr/wims/en_tool~number~calcnum.en.html">To display p(n) for n up to 41561, operate on "prime(n)"</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>
%H <a href="/A000040/a000040_1.html">Additional (less important) items -- comments, formulas, references, links, programs, etc. -- related to the prime numbers, A000040. [HTML version]</a> - <a href="/A000040/a000040_2.txt">[Plain text (TXT) version]</a>.
%F The prime number theorem is the statement that a(n) ~ n * log n as n -> infinity (Hardy and Wright, page 10).
%F For n >= 2, n*(log n + log log n - 3/2) < a(n); for n >= 20, a(n) < n*(log n + log log n - 1/2). [Rosser and Schoenfeld]
%F For all n, a(n) > n log n. [Rosser]
%F n log(n) + n (log log n - 1) < a(n) < n log n + n log log n for n >= 6. [Dusart, quoted in the Wikipedia article]
%F a(n) = n log n + n log log n + (n/log n)*(log log n - log n - 2) + O( n (log log n)^2/ (log n)^2). [Cipolla, see also Cesàro or the "Prime number theorem" Wikipedia article for more terms in the expansion]
%F a(n) = 2 + Sum_{k = 2..floor(2n*log(n)+2)} (1-floor(pi(k)/n)), for n > 1, where the formula for pi(k) is given in A000720 (Ruiz and Sondow 2002). - _Jonathan Sondow_, Mar 06 2004
%F I conjecture that Sum_{i>=1} (1/(prime(i)*log(prime(i)))) = Pi/2 = 1.570796327...; Sum_{i=1..100000} (1/(prime(i)*log(prime(i)))) = 1.565585514... It converges very slowly. - _Miklos Kristof_, Feb 12 2007
%F The last conjecture has been discussed by the math.research newsgroup recently. The sum, which is greater than Pi/2, is shown in sequence A137245. - _T. D. Noe_, Jan 13 2009
%F A000005(a(n)) = 2; A002033(a(n+1)) = 1. - _Juri-Stepan Gerasimov_, Oct 17 2009
%F A001222(a(n)) = 1. - _Juri-Stepan Gerasimov_, Nov 10 2009
%F From _Gary Detlefs_, Sep 10 2010: (Start)
%F Conjecture:
%F a(n) = {n| n! mod n^2 = n(n-1)}, n <> 4.
%F a(n) = {n| n!*h(n) mod n = n-1}, n <> 4, where h(n) = Sum_{k=1..n} 1/k. (End)
%F For n = 1..15, a(n) = p + abs(p-3/2) + 1/2, where p = m + int((m-3)/2), and m = n + int((n-2)/8) + int((n-4)/8). - _Timothy Hopper_, Oct 23 2010
%F a(2n) <= A104272(n) - 2 for n > 1, and a(2n) ~ A104272(n) as n -> infinity. - _Jonathan Sondow_, Dec 16 2013
%F Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n - 1) and 2^(n-1) mod n = 1}. - _Gary Detlefs_, May 25 2014
%F Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n - 1) and 2^(3*n) mod 3*n = 8}. - _Gary Detlefs_, May 28 2014
%F a(n) = 1 + Sum_{m=1..L(n)} (abs(n-Pi(m))-abs(n-Pi(m)-1/2)+1/2), where Pi(m) = A000720(m) and L(n) >= a(n)-1. L(n) can be any function of n which satisfies the inequality. For instance, L(n) can be ceiling((n+1)*log((n+1)*log(n+1))) since it satisfies this inequality. - _Timothy Hopper_, May 30 2015, Jun 16 2015
%F Satisfies a(n) = 2*n + Sum_{k=1..(a(n)-1)} cot(k*Pi/a(n))*sin(2*k*n^a(n)*Pi/a(n)). - _Ilya Gutkovskiy_, Jun 29 2016
%F Sum_{n>=1} 1/a(n)^s = P(s), where P(s) is the prime zeta function. - _Eric W. Weisstein_, Nov 08 2016
%F a(n) = floor(1 - log(-1/2 + Sum_{ d | A002110(n-1) } mu(d)/(2^d-1))/log(2)) where mu(d) = A008683(d). Golomb gave a proof in 1974: Give each positive integer a probability of W(n) = 1/2^n, then the probability M(d) of the integer multiple of number d equals 1/(2^d-1). Suppose Q = a(1)*a(2)*...*a(n-1) = A002110(n-1), then the probability of random integers that are mutually prime with Q is Sum_{ d | Q } mu(d)*M(d) = Sum_{ d | Q } mu(d)/(2^d-1) = Sum_{ gcd(m, Q) = 1 } W(m) = 1/2 + 1/2^a(n) + 1/2^a(n+1) + 1/2^a(n+2) + ... So ((Sum_{ d | Q } mu(d)/(2^d-1)) - 1/2)*2^a(n) = 1 + x(n), which means that a(n) is the only integer so that 1 < ((Sum_{ d | Q } mu(d)/(2^d-1)) - 1/2)*2^a(n) < 2. - _Jinyuan Wang_, Apr 08 2019
%p A000040 := n->ithprime(n); [ seq(ithprime(i),i=1..100) ];
%p # For illustration purposes only:
%p isPrime := s -> is(1 = sin(Pi*GAMMA(s)/s)/sin(Pi/s)):
%p select(isPrime, [$2..100]); # _Peter Luschny_, Feb 23 2018
%t Prime[Range[60]]
%o (Magma) [n : n in [2..500] | IsPrime(n)];
%o (Magma) a := func< n | NthPrime(n) >;
%o (PARI) {a(n) = if( n<1, 0, prime(n))};
%o (PARI) /* The following functions provide asymptotic approximations, one based on the asymptotic formula cited above (slight overestimate for n > 10^8), the other one based on pi(x) ~ li(x) = Ei(log(x)) (slight underestimate): */
%o prime1(n)=n*(log(n)+log(log(n))-1+(log(log(n))-2)/log(n)-((log(log(n))-6)*log(log(n))+11)/log(n)^2/2)
%o prime2(n)=solve(X=n*log(n)/2,2*n*log(n),real(eint1(-log(X)))+n)
%o \\ _M. F. Hasler_, Oct 21 2013
%o (PARI) forprime(p=2, 10^3, print1(p, ", ")) \\ _Felix Fröhlich_, Jun 30 2014
%o (PARI) primes(10^5) \\ _Altug Alkan_, Mar 26 2018
%o (Sage) a = sloane.A000040
%o a.list(58) # _Jaap Spies_, 2007
%o (Sage) prime_range(1, 300) # _Zerinvary Lajos_, May 27 2009
%o (Maxima) A000040(n) := block(
%o if n = 1 then return(2),
%o return( next_prime(A000040(n-1)))
%o )$ /* recursive, to be replaced if possible - _R. J. Mathar_, Feb 27 2012 */
%o (Haskell) See also Haskell Wiki Link
%o import Data.List (genericIndex)
%o a000040 n = genericIndex a000040_list (n - 1)
%o a000040_list = base ++ larger where
%o base = [2,3,5,7,11,13,17]
%o larger = p : filter prime more
%o prime n = all ((> 0) . mod n) $ takeWhile (\x -> x*x <= n) larger
%o _ : p : more = roll $ makeWheels base
%o roll (Wheel n rs) = [n * k + r | k <- [0..], r <- rs]
%o makeWheels = foldl nextSize (Wheel 1 [1])
%o nextSize (Wheel size bs) p = Wheel (size * p)
%o [r | k <- [0..p-1], b <- bs, let r = size*k+b, mod r p > 0]
%o data Wheel = Wheel Integer [Integer]
%o -- _Reinhard Zumkeller_, Apr 07 2014
%o (GAP)
%o A000040:=Filtered([1..10^5],IsPrime); # _Muniru A Asiru_, Sep 04 2017
%o (Python)
%o from sympy import primerange
%o print(list(primerange(2, 272))) # _Michael S. Branicky_, Apr 30 2022
%Y For is_prime and next_prime, see A010051 and A151800.
%Y Cf. A000720 ("pi"), A001223 (differences between primes), A002476, A002808, A003627, A006879, A006880, A008578, A233588.
%Y Cf. primes in lexicographic order: A210757, A210758, A210759, A210760, A210761.
%Y Cf. A003558, A179480 (relating to the Quasi-order theorem of Hilton and Pedersen).
%Y Boustrophedon transforms: A000747, A000732, A230953.
%Y a(2n) = A104272(n) - A233739(n).
%K core,nonn,nice,easy,changed
%O 1,1
%A _N. J. A. Sloane_
| 