This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000040 The prime numbers. (Formerly M0652 N0241) 8291

%I M0652 N0241

%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 n is prime if it is greater than 1 and has no positive divisors except 1 and n.

%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 sum of an odd number > 1 (2i+1, i >= 1) of consecutive positive odd numbers centered on the j-th odd number >= 2i+1 (2j+1, j >= i) being (2i+1)*(2j+1) has 2 or more odd prime factors (odd semiprime iff 2i+1 and 2j+1 are primes). - _Daniel Forgues_, Jul 15 2009

%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 1 is the empty product (has 0 prime factors), whereas a prime has 1 prime factor (itself). - _Daniel Forgues_, Jul 23 2009

%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 Elementary primality test: If no prime <= sqrt(m) divides m, then m is prime (since a prime is its own exclusive multiple, apart from 1). - _Lekraj Beedassy_, Mar 31 2005

%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 'Proton Arithmon'. - _Daniel Forgues_, May 08 2009

%C It appears that, with the Bachet-Bezout theorem, A000040 = (2*A039701) + (3*A157966). - _Eric Desbiaux_, Nov 15 2009

%C 2 and 3 might be referred to as the two "forcibly prime numbers" since there are no integers greater than 1 and less than or equal to their respective square roots. Not a single trial division ever needs to be done for 2 or 3, so they are disqualified from the outset from any attempt to belong to the set of composite numbers. 2 and 3 are thus the only consecutive primes. Since any further prime needs to be coprime to both 2 and 3, they must be congruent to 5 or 1 (mod 2*3) and thus must all be of the form (2*3)*k -/+ 1 with k >= 1. When both (2*3)*k - 1 and (2*3)*k + 1 are prime for a given k >= 1, they are referred to as twin primes (3 and 5 being the only twin primes of the form (2*2)*k - 1 and (2*2)*k + 1). - _Daniel Forgues_, Mar 19 2010

%C Conjecture: a(n) = (6*f(n) + (-1)^f(n)-3)/2, n > 2, where f(n) = floor(ithprime(n)/3) + 1. See A181709. - _Gary Detlefs_, Dec 12 2011

%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 <= p(n+1) are {k|k^f(n) mod primorial(n)=1}, where f(n)= LCM(p(i)-1,i=1..n) = A058254(n) and primorial(n) = A002110. For example, numbers with no prime divisor <= p(7)= 17 or, equivalently, the primes < 17^2 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 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

%C Numbers n such that ((n-2)!!)^2 == +-1 (mod n). - _Thomas Ordowski_, Aug 27 2016

%C Numbers n such that: ((n-2)!!)^4 == 1 (mod n). - _Richard R. Forberg_, Jul 12 2017

%C Does not satisfy Benford's law [Diaconis, 1977; Cohen-Katz, 1984; Berger-Hill, 2017]. - _N. J. A. Sloane_, Feb 07 2017

%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 A. Berger and T. P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64:

%D 2 (2017), 132-134.

%D D. M. Bressoud, Factorization and Primality Testing, Springer-Verlag NY 1989.

%D Ernesto Cesàro, "Sur une formule empirique de M. Pervouchine", Comptes rendus hebdomadaires des séances de l'Académie des sciences (in French), 119 (1894), 848-849.

%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 Daniel I. A. Cohen and Talbot M. Katz, "Prime numbers and the first digit phenomenon," J. Number Theory 18 (1984), 261-268.

%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 Seymour. B. Elk, "Prime Number Assignment to a Hexagonal Tessellation of a Plane That Generates Canonical Names for Peri-Condensed Polybenzenes", J. Chem. Inf. Comput. Sci., vol. 34 (1994), pp. 942-946.

%D W. & F. Ellison, Prime Numbers, Hermann Paris 1985

%D T. Estermann, Introduction to Modern Prime Number Theory, Camb. Univ. Press, 1969.

%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, Birkhaeuser 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="http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">alternate 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&amp;displaytype=printable&amp;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 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="http://primes.utm.edu/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>

%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>

%H D. Butler, <a href="http://www.tsm-resources.com/alists/prim.html">The first 2000 Prime Numbers</a>

%H C. K. Caldwell, <a href="http://primes.utm.edu/">The Prime Pages</a>: <a href="http://primes.utm.edu/glossary/page.php?sort=TablesOfPrimes">Tables of primes</a>; <a href="http://primes.utm.edu/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="http://primes.utm.edu/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 M. Chamness, <a href="http://www.alumni.caltech.edu/~chamness/prime.html">Prime number generator (Applet)</a>

%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="http://campmath.uqam.ca/infos2004/conf_double.pdf">Les nombres premiers: mysteres et consolation</a>

%H J.-M. De Koninck, <a href="http://campmath.uqam.ca/2005/nbPremMysEnj.pdf">Nombres premiers: mysteres 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 L. Euler, <a href="http://arXiv.org/abs/math.HO/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="http://www.walter-fendt.de/m14e/primes.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 L. & Y. Gallot, <a href="http://perso.wanadoo.fr/yves.gallot/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 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 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 & N. Saxena, Resonance 11-2002, <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>

%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 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 Tomas Svoboda, <a href="http://www.svobodat.com/primes/PRIMES1T.TXT">List of primes up to 10^6</a> [Slow link]

%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="http://www.lifl.fr/~wegrzyno/FormulPrem/FormulesPremiers23.html">Les formules simples qui donnent des nombres premiers en grande quantites</a>

%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(1/(p(i)*log(p(i)))) = Pi/2 = 1.570796327... Sum_{i = 1..100000}(1/(p(i)*log(p(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(1/k, k=1..n). (End)

%F First 15 primes; 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), 1<=n<=15. - _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 ceil((n+1)*log((n+1)*log(n+1))) since it satisfies this inequality. - _Timothy Hopper_, May 30 2015, Jun 16 2015

%F Sum_{n>=1} 1/a(n)^s = P(s), where P(s) is the prime zeta function. - _Eric W. Weisstein_, Nov 08 2016

%p A000040 := n->ithprime(n); [ seq(ithprime(i),i=1..100) ];

%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 (Sage) a = sloane.A000040; print a

%o print 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 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

%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

%O 1,1

%A _N. J. A. Sloane_, Apr 30 1991

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.