login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: seq:2,3,5,7
Displaying 1-10 of 2397 results found. page 1 2 3 4 5 6 7 8 9 10 ... 240
     Sort: relevance | references | number | modified | created      Format: long | short | data
A000040 The prime numbers.
(Formerly M0652 N0241) 		+20
7855
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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.

A number n is prime if it is greater than 1 and has no positive divisors except 1 and n.

A natural number is prime if and only if it has exactly two (positive) divisors.

A prime has exactly one proper positive divisor, 1.

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

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

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.

1 is the empty product (has 0 prime factors), whereas a prime has 1 prime factor (itself). - Daniel Forgues, Jul 23 2009

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.

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

Second sequence ever computed by electronic computer, on EDSAC, May 09 1949 (see Renwick link). - Russ Cox, Apr 20 2006

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

There is a unique decomposition of the primes: provided the weight A117078(n) is > 0, we have prime(n) = weight * level + gap, or A000040(n) = A117078(n) * A117563(n) + A001223(n). - Rémi Eismann, Feb 16 2007

Equals row sums of triangle A143350. - Gary W. Adamson, Aug 10 2008

APSO (Alternating partial sums of sequence) a-b+c-d+e-f+g... = (a+b+c+d+e+f+g...)-2*(b+d+f...): APSO(A000040) = A008347=A007504 - 2*(A077126 repeated) (A007504-A008347)/2 = A077131 alternated with A077126. - Eric Desbiaux, Oct 28 2008

The Greek transliteration of 'Prime Number' is 'Proton Arithmon'. - Daniel Forgues, May 08 2009

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

a(n) = A008864(n) - 1 = A052147(n) - 2 = A113395(n) - 3 = A175221(n) - 4 = A175222(n) - 5 = A139049(n) - 6 = A175223(n) - 7 = A175224(n) - 8 = A140353(n) - 9 = A175225(n) - 10. - Jaroslav Krizek, Mar 06 2010

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

For prime n, the sum of divisors of n > the product of divisors of n. Sigma(n)==1 (mod n). - Juri-Stepan Gerasimov, Mar 12 2011

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

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 definition has the advantage that it does not make an assertion on the number of divisors of n. It applies equally for the integers (where a prime has exactly four divisors) and the natural numbers (where a prime has exactly two divisors). - Peter Luschny, Oct 09 2012

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

Reading the primes (excluding 2,3,5) mod 90 divides them into 24 classes, which are described by A181732, A195993, A198382, A196000, A201804, A196007, A201734, A201739, A201819, A201816, A201817, A201818, A202104, A201820, A201822, A201101, A202113, A202105, A202110, A202112, A202129, A202114, A202115 and A202116. - J. W. Helkenberg, Jul 24 2013

The old definition of prime numbers was "positive integers that have no divisors other than 1 and itself", which gives A008578, not this sequence. - Omar E. Pol, Oct 05 2013

Questions on a(2n) and Ramanujan primes are in A233739. - Jonathan Sondow, Dec 16 2013

From Hieronymus Fischer, Apr 02 2014: (Start)

Natural numbers such that there is exactly one base b such that the base-b alternate digital sum is 0 (see A239707).

Equivalently: Numbers p > 1 such that b = p-1 is the only base >= 1 for which the base-b alternate digital sum is 0.

Equivalently: Numbers p > 1 such that the base-b alternate digital sum is <> 0 for all bases 1 <= b < p-1. (End)

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

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

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

The primes appear as the denominators of the only fractions in the table of integers and reduced fractions for: (k!/e) * Sum_{n>=0} Sum_{j=0..n} j^k/n!, k>=0, occurring at k=p-1, where p is a prime, with p=2 occurring at both k=1 and k=3. - Richard R. Forberg, Dec 23 2014.

The preceding comment also applies to the z-sequence of the Sheffer matrix, when multiplied by the factorial of its index. See A130190. - Richard R. Forberg, Dec 28 2014

It is easily proved that (a(n+m)^j + a(n)^k)/2 and (a(n+m)^j - a(n)^k)/2 are coprime for all m, j, k > 0 and n>1. Conjecture: All coprime pairs can be so constructed, assuming repeated division by 2 of the even number in the resulting pair until it is odd. - Richard R. Forberg, Jun 07 2015

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

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

Prime numbers are zeros of the functions V_s(x) = Sum_{n>=1} (moebius(n) / n^s) * x^(s*omega(n)), for each s > 1. - Dimitris Valianatos, Jun 29 2016

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

Numbers n such that ((n-2)!!)^2 == +-1 (mod n). - Thomas Ordowski, Aug 27 2016

REFERENCES

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.

E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I, Chaps. 8, 9.

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

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.

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 1.

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.

J.-P. Delahaye, Merveilleux nombres premiers, Pour la Science-Belin Paris, 2000.

J.-P. Delahaye, Savoir si un nombre est premier: facile, Pour La Science, 303(1) 2003, pp. 98-102.

M. Dietzfelbinger, Primality Testing in Polynomial Time, Springer NY 2004.

M. du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; see p. 5.

U. Dudley, Formulas for primes, Math. Mag., 56 (1983), 17-22.

J. Elie, "L'algorithme AKS", in 'Quadrature', No. 60, pp. 22-32, 2006 EDP-sciences, Les Ulis (France);

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.

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

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

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.

Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. (260-264).

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

M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972.

D. S. Jandu, Prime Numbers And Factorization, Infinite Bandwidth Publishing, N. Hollywood CA 2007.

Jones, James P., Daihachiro Sato, Hideo Wada, and Douglas Wiens. "Diophantine representation of the set of prime numbers." The American Mathematical Monthly 83, no. 6 (1976): 449-464. DOI: 10.2307/2318339, available from https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/JonesSatoWadaWiens.pdf.

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea, NY, 1974.

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. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.

W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, Chap. 6.

H. Lifchitz, Table des nombres premiers de 0 à 20 millions (Tomes I & II), Albert Blanchard, Paris 1971.

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

Kaoru Motose, On values of cyclotomic polynomials. II, Math. J. Okayama Univ. 37 (1995), 27-36.

P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag NY 1995.

P. Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004.

H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhaeuser Boston, Cambridge MA 1994.

B. Rittaud, "31415879. Ce nombre est-il premier?" ['Is this number prime?'], La Recherche, Vol. 361, pp. 70-73, Feb 15 2003, Paris.

D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, Chap. 1.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. Wells, Prime Numbers: The Most Mysterious Figures In Math, J.Wiley NY 2005.

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

LINKS

N. J. A. Sloane, Table of n, prime(n) for n = 1..10000

N. J. A. Sloane, Table of n, prime(n) for n = 1..100000

M. Agrawal, N. Kayal & N. Saxena, PRIMES is in P, Annals of Maths., 160:2 (2004), pp. 781-793. [alternate link]

M. Agrawal, A Short History of "PRIMES is in P"

P. Alfeld, Notes and Literature on Prime Numbers

J. W. Andrushkiw, R. I. Andrushkiw and C. E. Corzatt, Representations of Positive Integers as Sums of Arithmetic Progressions, Mathematics Magazine, Vol. 49, No. 5 (Nov., 1976), pp. 245-248.

Anonymous, Prime Number Master Index (for primes up to 2*10^7)

Anonymous, prime number

P. T. Bateman & H. G. Diamond, A Hundred Years of Prime Numbers, Amer. Math. Month., Vol. 103 (9), Nov. 1996, pp. 729-741.

E. R. Berlekamp, A contribution to mathematical psychometrics, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]

D. J. Bernstein, Proving Primality After Agrawal-Kayal-Saxena

D. J. Bernstein, Distinguishing prime numbers from composite numbers

P. Berrizbeitia, Sharpening "Primes is in P" for a large family of numbers, arXiv:math/0211334 [math.NT], 2002.

A. Booker, The Nth Prime Page

F. Bornemann, PRIMES Is in P: A Breakthrough for "Everyman"

A. Bowyer, Formulae for Primes [broken link ?]

B. M. Bredikhin, Prime number

R. P. Brent, Primality testing and integer factorization

J. Britton, Prime Number List

D. Butler, The first 2000 Prime Numbers

C. K. Caldwell, The Prime Pages

C. K. Caldwell, Tables of primes

C. K. Caldwell, The first 10000 primes

C. K. Caldwell, The first 50,000,000 primes in batches of 1,000,000 (Primes up to 982,451,653.)

C. K. Caldwell, A Primality Test

C. K. Caldwell and Y. Xiong, What is the smallest prime?, J. Integer Seq. 15 (2012), no. 9, Article 12.9.7 and arXiv:1209.2007 [math.HO], 2012.

Chris K. Caldwell, Angela Reddick, Yeng Xiong and Wilfrid Keller, The History of the Primality of One: A Selection of Sources, Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.

M. Chamness, Prime number generator (Applet)

P. Cox, Primes is in P

P. J. Davis & R. Hersh, The Mathematical Experience, The Prime Number Theorem

J.-M. De Koninck, Les nombres premiers: mysteres et consolation

J.-M. De Koninck, Nombres premiers: mysteres et enjeux

J.-P. Delahaye, Formules et nombres premiers

Pierre Dusart, Autour de la fonction qui compte le nombre de nombres premiers, Thèse, Université de Limoges, France, (1998).

Pierre Dusart, The k-th prime is greater than k(ln k + ln ln k-1) for k>=2, Mathematics of Computation 68: (1999), 411-415.

J. Elie, L'algorithme AKS ou Les nombres premiers sont de classe P

L. Euler, Observations on a theorem of Fermat and others on looking at prime numbers, arXiv:math/0501118 [math.HO], 2005-2008.

W. Fendt, Table of Primes from 1 to 1000000000000

P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function, arXiv:math/0501379 [math.CO], 2005.

J. Flamant, Primes up to one million

K. Ford, Expositions of the PRIMES is in P theorem.

L. & Y. Gallot, The Chronology of Prime Number Records

P. Garrett, Big Primes, Factoring Big Integers

P. Garrett, Naive Primality Test

P. Garrett, Listing Primes

N. Gast, PRIMES is in P: Manindra Agrawal, Neeraj Kayal and Nitin Saxena (in French)

D. A. Goldston, S. W. Graham, J. Pintz and C. Y. Yildirim, Small gaps between primes and almost primes, arXiv:math/0506067 [math.NT], 2005.

A. Granville, It is easy to determine whether a given integer is prime [alternate link]

P. Hartmann, Prime number proofs (in German)

Haskell Wiki, Prime Numbers

ICON Project, List of first 50000 primes grouped within ten columns

N. Kayal & N. Saxena, Resonance 11-2002, A polynomial time algorithm to test if a number is prime or not

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.

W. Liang & H. Yan, Pseudo Random test of prime numbers, arXiv:math/0603450 [math.NT], 2006.

J. Malkevitch, Primes

Mathworld Headline News, Primality Testing is Easy

K. Matthews, Generating prime numbers

Y. Motohashi, Prime numbers-your gems, arXiv:math/0512143 [math.HO], 2005.

J. Moyer, Some Prime Numbers

C. W. Neville, New Results on Primes from an Old Proof of Euler's, arXiv:math/0210282 [math.NT], 2002-2003.

L. C. Noll, Prime numbers, Mersenne Primes, Perfect Numbers, etc.

M. A. Nyblom and C. Evans, On the enumeration of partitions with summands in arithmetic progression, Australasian Journal of Combinatorics, Vol. 28 (2003), pp. 149-159.

J. J. O'Connor & E. F. Robertson, Prime Numbers

M. E. O'Neill, The Genuine Sieve of Eratosthenes, J. of Functional Programming, Vol 19 Issue 1, Jan 2009, p. 95ff, CUP NY

M. Ogihara & S. Radziszowski, Agrawal-Kayal-Saxena Algorithm for Testing Primality in Polynomial Time

P. Papaphilippou, Plotter of prime numbers frequency graph (flash object) [From Philippos Papaphilippou (philippos(AT)safe-mail.net), Jun 02 2010]

J. M. Parganin, Primes less than 50000

Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.

Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]

I. Peterson, Prime Pursuits

Omar E. Pol, Illustration of initial terms

Omar E. Pol, Sobre el patrón de los números primos, and from Jason Davies, An interactive companion (for primes 2..997)

Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. [Annotated and scanned copy]

Primefan, The First 500 Prime Numbers

Primefan, Script to Calculate Prime Numbers

Project Gutenberg Etext, First 100,000 Prime Numbers

C. D. Pruitt, Formulae for Generating All Prime Numbers

R. Ramachandran, Frontline 19 (17) 08-2000, A Prime Solution

W. S. Renwick, EDSAC log.

F. Richman, Generating primes by the sieve of Eratosthenes

Barkley Rosser, Explicit Bounds for Some Functions of Prime Numbers, American Journal of Mathematics 63 (1941) 211-232.

J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. Volume 6, Issue 1 (1962), 64-94.

S. M. Ruiz and J. Sondow, Formulas for pi(n) and the n-th prime, arXiv:math/0210312 [math.NT], 2002-2014.

S. O. S. Math, First 1000 Prime Numbers

A. Schulman, Prime Number Calculator

M. Slone, PlanetMath.Org, First thousand positive prime numbers

A. Stiglic, The PRIMES is in P little FAQ

Zhi-Wei Sun, On functions taking only prime values, J. Number Theory, 133 (2013), no. 8, 2794-2812.

Zhi-Wei Sun, A conjecture on unit fractions involving primes, Preprint 2015.

Tomas Svoboda, List of primes up to 10^6 [Slow link]

J. Teitelbaum, Review of "Prime numbers:A computational perspective" by R. Crandall & C. Pomerance

J. Thonnard, Les nombres premiers(Primality check; Closest next prime; Factorizer)

J. Tramu, Movie of primes scrolling

A. Turpel, Aesthetics of the Prime Sequence [broken link ?]

S. Wagon, Prime Time: Review of "Prime Numbers:A Computational Perspective" by R. Crandall & C. Pomerance

M. R. Watkins, unusual and physical methods for finding prime numbers

S. Wedeniwski, Primality Tests on Commutator Curves

E. Wegrzynowski, Les formules simples qui donnent des nombres premiers en grande quantites

Eric Weisstein's World of Mathematics, Prime Number.

Eric Weisstein's World of Mathematics, Prime-Generating Polynomial

Eric Weisstein's World of Mathematics, Prime Spiral

Wikipedia, Prime number

G. Xiao, Primes server, Sequential Batches Primes Listing (up to orders not exceeding 10^308)

G. Xiao, Numerical Calculator, To display p(n) for n up to 41561, operate on "prime(n)"

Index entries for "core" sequences

FORMULA

The prime number theorem is the statement that a(n) ~ n * log n as n -> infinity (Hardy and Wright, page 10).

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]

For all n, a(n) > n log n. [Rosser]

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]

a(n) = n log n + n log log n + (n/log n)*(log log n - log 2 - 2) + O( n (log log n)^2/ (log n)^2). [Cipoli, quoted in the Wikipedia article]

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

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

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

A000005(a(n)) = 2; A002033(a(n+1)) = 1. - Juri-Stepan Gerasimov, Oct 17 2009

A001222(a(n)) = 1. - Juri-Stepan Gerasimov, Nov 10 2009

From Gary Detlefs, Sep 10 2010: (Start)

Conjecture:

a(n) = {n| n! mod n^2 = n(n-1)}, n <> 4.

a(n) = {n| n!*h(n) mod n = n-1}, n<>4, where h(n) = sum(1/k, k=1..n). (End)

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

a(2n) <= A104272(n) - 2 for n > 1, and a(2n) ~ A104272(n) as n -> infinity. - Jonathan Sondow, Dec 16 2013

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

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

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

MAPLE

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

MATHEMATICA

Prime[Range[60]]

primitiveElements[lst_List] := Block[{lsu = {lst[[1]]}, lsv = Rest@ lst}, While[ Length@ lsv > 0, If [Min@ Mod[ lsv[[1]], lsu] != 0, AppendTo[ lsu, lsv[[1]] ]]; lsv = Rest@ lsv]; lsu]; primitiveElements[ Range[2, 275]] (* or *)

NestList[ NextPrime, 2, 57] (* Robert G. Wilson v, Aug 16 2014 *)

PROG

(MAGMA) [n : n in [2..500] | IsPrime(n)];

(MAGMA) a := func< n | NthPrime(n) >;

(PARI) {a(n) = if( n<1, 0, prime(n))};

(Sage) a = sloane.A000040; print a

print a.list(58) # Jaap Spies, 2007

(Sage) prime_range(1, 300) # Zerinvary Lajos, May 27 2009

(Maxima) A000040(n) := block(

    if n = 1 then return(2),

    return( next_prime(A000040(n-1)))

    )$ /* recursive, to be replaced if possible - R. J. Mathar, Feb 27 2012 */

From M. F. Hasler, Oct 21 2013: (Start) The following PARI code provides 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):

(PARI) 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)

(PARI) prime2(n)=solve(X=n*log(n)/2, 2*n*log(n), real(eint1(-log(X)))+n) \\ (End)

(Haskell)  See also Haskell Wiki Link

import Data.List (genericIndex)

a000040 n = genericIndex a000040_list (n - 1)

a000040_list = base ++ larger where

   base   = [2, 3, 5, 7, 11, 13, 17]

   larger = p : filter prime more

   prime n = all ((> 0) . mod n) $ takeWhile (\x -> x*x <= n) larger

   _ : p : more = roll $ makeWheels base

   roll (Wheel n rs) = [n * k + r | k <- [0..], r <- rs]

   makeWheels = foldl nextSize (Wheel 1 [1])

   nextSize (Wheel size bs) p = Wheel (size * p)

       [r | k <- [0..p-1], b <- bs, let r = size*k+b, mod r p > 0]

data Wheel = Wheel Integer [Integer]

-- Reinhard Zumkeller, Apr 07 2014

(PARI) forprime(p=2, 10^3, print1(p, ", ")) \\ Felix Fröhlich, Jun 30 2014

CROSSREFS

Cf. A002808, A008578, A006879, A006880, A000720 ("pi"), A001223 (differences between primes), A233588.

Cf. primes in lexicographic order: A210757, A210758, A210759, A210760, A210761.

Cf. A003558, A179480 (relating to the Quasi-order theorem of Hilton and Pedersen).

Boustrophedon transforms: A000747, A000732, A230953.

a(2n) = A104272(n) - A233739(n).

KEYWORD

core,nonn,nice,easy

AUTHOR

N. J. A. Sloane, Apr 30 1991

STATUS

approved

A000041 a(n) = number of partitions of n (the partition numbers).
(Formerly M0663 N0244) 		+20
2018
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also number of nonnegative solutions to b + 2c + 3d + 4e + ... = n and the number of nonnegative solutions to 2c + 3d + 4e + ... <= n. - Henry Bottomley, Apr 17 2001

a(n) is also the number of conjugacy classes in the symmetric group S_n (and the number of irreducible representations of S_n).

Also the number of rooted trees with n+1 nodes and height at most 2.

Coincides with the sequence of numbers of nilpotent conjugacy classes in the Lie algebras gl(n). A006950, A015128 and this sequence together cover the nilpotent conjugacy classes in the classical A,B,C,D series of Lie algebras. - Alexander Elashvili, Sep 08 2003

a(n) = a(0)b(n) + a(1)b(n-2) + a(2)b(n-4) + ... where b = A000009.

Number of distinct Abelian groups of order p^n, where p is prime (the number is independent of p). - Lekraj Beedassy, Oct 16 2004

Number of graphs on n vertices that do not contain P3 as an induced subgraph. - Washington Bomfim, May 10 2005

It is unknown if there are infinitely many partition numbers divisible by 3, although it is known that there are infinitely many divisible by 2. - Jonathan Vos Post, Jun 21 2005

Numbers of terms to be added when expanding the n-th derivative of 1/f(x). - Thomas Baruchel, Nov 07 2005

a(n) = A114099(9*n). - Reinhard Zumkeller, Feb 15 2006

Sequence agrees with expansion of Molien series for symmetric group S_n up to the term in x^n. - Maurice D. Craig (towenaar(AT)optusnet.com.au), Oct 30 2006

Also the number of nonnegative integer solutions to x_1 + x_2 + x_3 + ... + x_n = n such that n >= x_1 >= x_2 >= x_3 >= ... >= x_n >= 0, because by letting y_k = x_k - x_(k+1) >= 0 (where 0 < k < n) we get y_1 + 2y_2 + 3y_3 + ... + (n-1)y_(n-1) + nx_n = n. - Werner Grundlingh (wgrundlingh(AT)gmail.com), Mar 14 2007

Let P(z) := Sum_{j>=0} b_j z^j, b_0 != 0. Then 1/P(z) = Sum_{j>=0} c_j z^j, where the c_j must be computed from the infinite triangular system b_0 c_0 = 1, b_0 c_1 + b_1 c_0 = 0 and so on (Cauchy products of the coefficients set to zero). The n-th partition number arises as the number of terms in the numerator of the expression for c_n: The coefficient c_n of the inverted power series is a fraction with b_0^(n+1) in the denominator and in its numerator having a(n) products of n coefficients b_i each. The partitions may be read off from the indices of the b_i. - Peter C. Heinig (algorithms(AT)gmx.de), Apr 09 2007

A026820(a(n),n) = A134737(n) for n > 0. - Reinhard Zumkeller, Nov 07 2007

Equals row sums of triangle A137683. - Gary W. Adamson, Feb 05 2008

a(n) = the number of different ways to run up a staircase with n steps, taking steps of sizes 1, 2, 3, ... and r (r <= n), where the order is not important and there is no restriction on the number or the size of each step taken. - Mohammad K. Azarian, May 21 2008

Equals the eigenvector of triangle A145006 and row sums of the eigentriangle of the partition numbers, A145007. - Gary W. Adamson, Sep 28 2008

Starting with offset 1 = INVERT transform of (1, 1, 0, 0, -1, 0, -1,...), where A080995, the characteristic function of A001318 (1, 2, 5, 7, 12,...) is signed (++ -- ++,...) as to 1's. This is equivalent to Lim__{n=1..inf} A145006^n as a vector. The INVERT transform of (1, 1, 0, 0, -1,...) begins (1, 2,..) then for each successive operation we take a dot product of (1, 1, 0, 0, -1,...) in reverse and the ongoing results of our series (1, 2, 3, 5, 7,...) then add the result to the next term in (1, 1, 0, 0, -1,...). For example, a (7) = 15 = (0, -1, 0, 0, 1, 1) dot (1, 2, 3, 5, 7, 11) = (0*1, (-1)*2, 0*3, 0*5, 1*7, 1*11) = (-2 + 7 + 11) = 16, then add to (-1) = 15. - Gary W. Adamson, Oct 05 2008

Convolved with A147843 = A000203 prefaced with a zero: (0, 1, 3, 4, 7,...). - Gary W. Adamson, Nov 15 2008

Equals an infinite convolution product_(1, 1, 1, ...)*(1, 0, 1, 0, 1, ...)*(1, 0, 0, 1, 0, 0, 1, ...)*(1, 0, 0, 0, 1, 0, 0, 0, 1, ...)*...; = a*b*c*...; where a = (1/(1-x)), b = (1/(1-x^2)), c = (1/(1-x^3)), etc. An array by rows: row 1 = a, row 2 = a*b, row 3 = a*b*c, ...; gives:

1, 1, 1, 1, 1, 1,  1,  1,  1,  1, ... = (a)

1, 1, 2, 2, 3, 3,  4,  4,  5,  5, ... = (a*b)

1, 1, 2, 3, 4, 5,  7,  8, 10, 11, ... = (a*b*c)

1, 1, 2, 3, 4, 5,  6,  9, 11, 17, ... = (a*b*c*d)

1, 1, 2, 3, 5, 5,  7, 10, 13, 18, ... = (a*b*c*d*e)

1, 1, 2, 3, 5, 7, 11, 14, 20, 25, ... = (a*b*c*d*e*f)

1, 1, 2, 3, 5, 7, 11, 15, 21, 27, ... = (a*b*c*d*e*f*g)

1, 1, 2, 3, 5, 7, 11, 15, 22, 28, ... = (a*b*c*d*e*f*g*h)

1, 1, 2, 3, 5, 7, 11, 15, 22, 29, ... = (a*b*c*d*e*f*g*h*i)

  ... with rows tending to A000041. Partition triangles A058398 = ascending antidiagonals. Partition triangle A008284 reversal of A058398. - Gary W. Adamson, Jun 12 2009

Starting with offset 1 = row sums of triangle A168532. - Gary W. Adamson, Nov 28 2009

a(n) = A026820(n, n); a(n) = A108949(n) + A045931(n) + A108950(n) = A130780(n) + A171966(n) - A045931(n) = A045931(n) + A171967(n). - Reinhard Zumkeller, Jan 21 2010

P(x) = A(x)/A(x^2) with P(x) = (1+x+2x^2+3x^3+5x^4+7x^5 + ...),

  and A(x) = (1+x+3x^2+4x^3+10x^4+13x^5 + ...),

  and A(x^2) = (1+x^2+3x^4+4x^6+10x^8+ ...), where A092119 = (1, 1, 3, 4, 10,...) = Euler transform of the ruler sequence, A001511. - Gary W. Adamson, Feb 11 2010

Equals row sums of triangle A173304. - Gary W. Adamson, Feb 15 2010

p(x) = A(x)*A(x^2), A(x) = A174065; p(x) = B(x)*B(x^3), B(x) = A174068. Equals row sums of triangles A174066 and A174067. - Gary W. Adamson, Mar 06 2010

Triangle A113685 is equivalent to p(x) = p(x^2) * A000009(x). Triangle A176202 is equivalent to p(x) = p(x^3) * A000726(x). - Gary W. Adamson, Apr 11 2010

A sequence of positive integers p = p_1 ... p_k is a descending partition of the positive integer n if p_1 + ... + p_k = n and p_1 >= ... >= p_k. If formally needed p_j = 0 is appended to p for j > k. Let P_n denote the set of these partition for some n >= 1. Then a(n) = 1 + Sum_{p in P_n} floor((p_1-1)/(p_2+1)). (Cf. A000065, where the formula reduces to the sum.) Proof in Kelleher and O'Sullivan (2009). For example a(6) = 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 2 + 5 = 11. - Peter Luschny, Oct 24 2010

Let n = sum( k_(p_m) p_m )=k_1 + 2k_2 + 5k_5 + 7k_7 + ..., where p_m is the m-th generalized pentagonal number (A001318). Then a(n) is the sum over all such pentagonal partitions of n of (-1)^(k_5+k_7 + k_22 + ...) ( k_1 + k_2 + k_5 + ...)! /( k_1! k_2! k_5!  ...), where the exponent of (-1) is the sum of all the k's corresponding to even-indexed GPN's. - Jerome Malenfant, Feb 14 2011

The matrix of a(n) values

  a(0)

  a(1) a(0)

  a(2) a(1) a(0)

  a(3) a(2) a(1) a(0)

  ....

  a(n) a(n-1) a(n-2)...a(0)

is the inverse of the matrix

   1

  -1  1

  -1 -1  1

   0 -1 -1  1

  ....

  -d_n  -d_(n-1) -d_(n-2) ...-d_1 1

where d_q = (-1)^(m+1) if q = m(3m-1)/2 = the m-th generalized pentagonal number (A001318), = 0 otherwise. - Jerome Malenfant, Feb 14 2011

Equals row sums of triangle A187566. - Gary W. Adamson, Mar 21 2011

Let k > 0 be an integer, and let i_1, i_2, ..., i_k be distinct integers such that 1 <= i_1 < i_2 < ... < i_k. Then, equivalently, a(n) equals the number of partitions of N = n + i_1 + i_2 + ... + i_k in which each i_j (1 <= j <= k) appears as a part at least once. To see this, note that the partitions of N of this class must be in 1-to-1 correspondence with the partitions of n, since N - i_1 - i_2 - ... - i_k = n. - L. Edson Jeffery, Apr 16 2011

a(n) is the number of distinct degree sequences over all free trees having n + 2 nodes.  Take a partition of the integer n, add 1 to each part and append as many 1's as needed so that the total is 2n + 2.  Now we have a degree sequence of a tree with n + 2 nodes.  Example: The partition 3 + 2 + 1 = 6 corresponds to the degree sequence {4, 3, 2, 1, 1, 1, 1, 1} of a tree with 8 vertices. - Geoffrey Critzer, Apr 16 2011

a(n) is number of distinct characteristic polynomials among  n! of permutations matrices size n X n. - Artur Jasinski, Oct 24 2011

Conjecture: starting with offset 1 represents the numbers of ordered compositions of n using the signed (++--++...) terms of A001318 starting (1, 2, -5, -7, 12, 15,...). - Gary W. Adamson, Apr 04 2013 (this is true by the pentagonal number theorem, Joerg Arndt, Apr 08 2013)

a(n) is also number of terms in expansion of the n-th derivative of log(f(x)). In Mathematica notation: Table[Length[Together[f[x]^n * D[Log[f[x]], {x, n}]]], {n, 1, 20}]. - Vaclav Kotesovec, Jun 21 2013

Conjecture: No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013

Partitions of n that contain a part p are the partitions of n - p.  Thus, number of partitions of m*n - r that include k*n as a part is A000041(h*n-r), where h = m - k >= 0, n >= 2, 0 <= r < n; see A111295 as an example.  - Clark Kimberling, Mar 03 2014

a(n) is the number of compositions of n into positive parts avoiding the pattern [1, 2]. - Bob Selcoe, Jul 08 2014

Conjecture: For any j there exists k such that all primes p <= A000040(j) are factors of one or more a(n) <= a(k). Growth of this coverage is slow and irregular. k = 1067 covers the first 102 primes, thus slower than A000027. - Richard R. Forberg, Dec 08 2014

a(n) is the number of nilpotent conjugacy classes in the order-preserving, order-decreasing and (order-preserving and order-decreasing) injective transformation semigroups. - Ugbene Ifeanyichukwu, Jun 03 2015

From Gregory L. Simay, Nov 08 2015: (Start)

Define a segmented partition a(n,k, <s(1)..s(j)>) to be a partition of n with exactly k parts, with s(j) parts t(j) identical to each other and distinct from all the other parts. Note that n>=k, j<=k, 0<=s(j)<=k,  s(1)t(1) +..+ s(j)t(j) = n and s(1)+..+s(j)=k. Then there are up to a(k) segmented partitions of n with exactly k parts.

(End)

From Gregory L. Simay, Nov 09 2015: (Start)

The polynomials for a(n,k,<s(1),..s(j)> have degree j-1.

  a(n,k,<k>) = 1 if n=0modk, =0 otherwise

  a(rn,rk,<r*s(1),..,r*s(j)>) = a(n,k,<s(1),..,s(j)>)

  a(n odd, k, <all s(j) even>) = 0

Established results can be recast in terms of segmented partitions:

  For j(j+1)/2 <= n < (j+1)(j+2)/2, A000009(n) = a(n,1,<1>) +..+ a(n,j,<j 1's>), j<n

  a(n,k, <j 1's> = a(n - j(j-1)/2, k)

(End)

a(10^20) was computed using the NIST Arb package. It has 11140086260 digits and its head and tail sections are 18381765...88091448. See the Johansson 2015 link. - Stanislav Sykora, Feb 01 2016

REFERENCES

George E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, Mass., 1976.

G. E. Andrews and K. Ericksson, Integer Partitions, Cambridge University Press 2004.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 307.

R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; Chapter III.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.

B. C. Berndt, Number Theory in the Spirit of Ramanujan, Chap. I Amer. Math. Soc. Providence RI 2006.

J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 183.

L. E. Dickson, History of the Theory of Numbers, Vol.II Chapter III pp. 101-164,Chelsea NY 1992.

F. J. Dyson, Some guesses in the theory of partitions, Eureka, 8 (1944), 10-15.

N. J. Fine, Basic Hypergeometric Series and Applications, Amer. Math. Soc., 1988; p. 37, Eq. (22.13).

H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.

G. H. Hardy and S. Ramanujan, Asymptotic formulas in combinatorial analysis, Proc. London Math. Soc., 17 (1918), 75-.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (Fifth  edition), Oxford Univ. Press (Clarendon), 1979, 273-296.

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.4, p. 396.

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.1, p. 491.

S. Ramanujan, Collected Papers, Chap. 25, Cambridge Univ. Press 1927 (Proceedings of the Camb.Phil.Soc., 19 (1919), pp. 207-213).

S. Ramanujan, Collected Papers, Chap. 28, Cambridge Univ. Press 1927 (Proceedings of the London Math.Soc., 2, 18(1920)).

S. Ramanujan, Collected Papers, Chap. 30, Cambridge Univ. Press 1927 (Mathematische Zeitschrift, 9 (1921), pp. 147-163).

S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. See Table IV on page 308.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 122.

J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.

J. E. Roberts, Lure of the Integers, pp. 168-9 MAA 1992.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. E. Tapscott and D. Marcovich, "Enumeration of Permutational Isomers: The Porphyrins", Journal of Chemical Education, 55 (1978), 446-447.

Robert M. Young, "Excursions in Calculus", Mathematical Association of America, p. 367.

LINKS

David W. Wilson, Table of n, a(n) for n = 0..10000

Joerg Arndt, Matters Computational (The Fxtbook), section 16.4, pp.344-353

Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, p. 836. [scanned copy]

Scott Ahlgren and Ken Ono, Addition and Counting: The Arithmetic of Partitions

Scott Ahlgren and Ken Ono, Congruence properties for the partition function

Scott Ahlgren and Ken Ono, Congruence properties for the partition function, PNAS, vol. 98 no. 23, 12882-12884.

Gert Almkvist, Asymptotic formulas and generalized Dedekind sums, Exper. Math., 7 (No. 4, 1998), pp. 343-359.

Gert Almkvist, On the differences of the partition function, Acta Arith., 61.2 (1992), 173-181.

Gert Almkvist and Herbert S. Wilf, On the coefficients in the Hardy-Ramanujan-Rademacher formula for p(n)

Amazing Mathematical Object Factory, Information on Partitions

George E. Andrews, Three Aspects of Partitions, Séminaire Lotharingien de Combinatoire, B25f (1990), 1 p.

George E. Andrews, On a Partition Function of Richard Stanley, The Electronic Journal of Combinatorics, Volume 11, Issue 2 (2004-6) (The Stanley Festschrift volume), Research Paper #R1.

George E. Andrews and Ken Ono, Ramanujan's congruences and Dyson's crank

George E. Andrews and Ranjan Roy, Ramanujan's Method in q-series Congruences, The Electronic Journal of Combinatorics, Volume 4, Issue 2 (1997) (The Wilf Festschrift volume) > Research Paper #R2

Anonymous, Bibliography on Partitions

A. O. L. Atkins and F. G. Garvan, Relations between the ranks and cranks of partitions, arXiv:math/0208050 [math.NT], 2002.

Alexander Berkovich and Frank G. Garvan, On the Andrews-Stanley Refinement of Ramanujan's Partition Congruence Modulo 5, arXiv:math/0401012 [math.CO], 2004.

Alexander Berkovich and Frank G. Garvan, On the Andrews-Stanley Refinement of Ramanujan's Partition Congruence Modulo 5 and Generalizations, arXiv:math/0402439 [math.CO], 2004.

Bruce C. Berndt, Ramanujan's congruences for the partition function modulo 5,7 and 11

Bruce C. Berndt and K. Ono, Ramanujan's Unpublished Manuscript On The Partition And Tau Functions With Proofs And Commentary

Bruce C. Berndt and K. Ono, Ramanujan's Unpublished Manuscript on the Partition and Tau Functions with Proofs and Commentary, Séminaire Lotharingien de Combinatoire, B42c (1999), 63 pp.

Henry Bottomley, Illustration of initial terms

Henry Bottomley, Illustration of initial terms of A000009, A000041 and A047967

Henry Bottomley, Partition and composition calculator [broken link]

Kevin S. Brown, Additive Partitions of Numbers [Broken link]

Kevin S. Brown, Additive Partitions of Numbers [Cached copy of lost web page]

Kevin S. Brown's Mathpages, Computing the Partitions of n

Jan Hendrik Bruinier, Amanda Folsom, Zachary A. Kent and Ken Ono, Recent work on the partition function

Jan Hendrik Bruinier and Ken Ono, Algebraic formulas for the coefficients of half-integral weight harmonic weak Maass forms

Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.

Yuriy Choliy and Andrew V. Sills, A formula for the partition function that 'counts'.

Lynn Chua and Krishanu Roy Sankar, Equipopularity Classes of 132-Avoiding Permutations, The Electronic Journal of Combinatorics 21(1)(2014), #P59. [Cited by Shalosh B. Ekhad and Doron Zeilberger, 2014] - N. J. A. Sloane, Mar 31 2014

Jimena Davis and Elizabeth Perez, Computations Of The Partition Function, p(n)

Shalosh B. Ekhad and Doron Zeilberger, Automatic Proofs of Asymptotic Abnormality (and much more!) of Natural Statistics Defined on Catalan-Counted Combinatorial Families, arXiv:1403.5664 [math.CO], 2014.

FindStat - Combinatorial Statistic Finder, Integer partitions

Nathan J. Fine, Some New Results On Partitions

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 41

Amanda Folsom, Zachary A. Kent and Ken Ono, ''l''-adic properties of the partition function. In press.

Amanda Folsom, Zachary A. Kent and Ken Ono, ''l''-adic properties of the partition function, Adv. Math. 229 (2012) 1586

B. Forslund, Partitioning Integers

Harald Fripertinger, Partitions of an Integer

GEO magazine, Zahlenspalterei

James Grime and Brady Haran, Partitions - Numberphile (2016)

A. Hassen and T. J. Olsen, Playing With Partitions On The Computer

A. D. Healy, Partition Identities

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 61 and Encyclopedia of Combinatorial Structures 74 [broken links]

Fredrik Johansson, Fast arbitrary-precision evaluation of special functions in the Arb library, OPSFA13, NIST, June 2015, page 15.

Jonthan M. Kane, Distribution of orders of Abelian groups, Math. Mag., 49 (1976), 132-135.

Jerome Kelleher and Barry O'Sullivan, Generating All Partitions: A Comparison Of Two Encodings, arXiv:0909.2331 [cs.DS], 2009-2014.

Erica Klarreich, Pieces of Numbers: A proof brings closure to a dramatic tale of partitions and primes, Science News, Week of Jun 18, 2005; Vol. 167, No. 25, p. 392.

Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015.

J. Laurendi, Partitions of Integers

Oleg Lazarev, Matt Mizuhara, Ben Reid, Some Results in Partitions, Plane Partitions, and Multipartitions

T. Lockette, Explore Magazine, Path To Partitions

Jerome Malenfant, Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers, arXiv:1103.1585 [math.NT], 2011.

Dr. Math, Partitioning the Integers and Partitioning an Integer

M. MacMahon, Collected Papers of Ramanujan, Table for p(n);n=1 through 200

S. Markovski and M. Mihova, An explicit formula for computing the partition numbers p(n), Math. Balkanica 22 (2008) 101-119 MR2467361

Johannes W. Meijer, Euler's ship on the Pentagonal Sea, pdf and jpg.

Johannes W. Meijer and Manuel Nepveu, Euler's ship on the Pentagonal Sea, Acta Nova, Volume 4, No.1, December 2008. pp. 176-187.

Gerard P. Michon, Table of partition function p(n) (n=0 through 4096)

Gerard P. Michon, Partition function

G. A. Miller, Number of the abelian groups of a given order

Hisanori Mishima, Factorization of Partition Numbers

T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

D. J. Newman, A simplified proof of the partition formula, Michigan Math. J. 9:3 (1962), pp. 193-287.

OEIS Wiki, Sorting numbers

Ken Ono, Arithmetic of the partition function

Ken Ono, Parity of the partition function, Electron. Res. Announc. Amer. Math. Soc. 1 (1995), 35-42.

Ken Ono, Distribution of the partition function modulo m, Annals Math. 151 (2000), 293-307

Ken Ono (with J. Bruinier, A. Folsom and Z. Kent), Emory University, Adding and counting

T. J. Osler, Playing with Partitions on the Computer

I. Pak, Partition bijections, a survey, Ramanujan J. 12 (2006) 5-75

I. Peterson, The Power Of Partitions

Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Michel Planat, Quantum 1/f Noise in Equilibrium: from Planck to Ramanujan, arXiv:math-ph/0307033, 2003.

Simon Plouffe, Partitions [Contains first 10000000 terms]

Simon Plouffe, Partition numbers through n = 300000; Partitions numbers from 300000 to 450000; Partitions numbers from 450000 to 500000

M. Presern, Some Results On Partitions

W. A. Pribitkin, The Ramanujan Journal 4(4) 2000, Revisiting Rademacher's Formula for the Partition Function p(n)

PYTHAGORAS, Ramanujan and The Partition Function(Text in Dutch)

Srinivasa Ramanujan, Some Properties Of p(n), The Number Of Partitions Of n

Srinivasa Ramanujan, Congruence Properties Of Partitions

Srinivasa Ramanujan, Congruence Properties Of Partitions

Srinivasa Ramanujan and G. H. Hardy, Une formule asymptotique pour le nombre de partitions de n

J. D. Rosenhouse, Partitions of Integers

J. D. Rosenhouse, Solutions to Problems

Kate Rudolph, Pattern Popularity in 132-Avoiding Permutations, The Electronic Journal of Combinatorics 20(1)(2013), #P8. [Cited by Shalosh B. Ekhad and Doron Zeilberger, 2014] - N. J. A. Sloane, Mar 31 2014

F. Ruskey, Generate Numerical Partitions

F. Ruskey, The first 284547 partition numbers (52MB compressed file)

M. Savic, The Partition Function and Ramanujan's 5k+4 Congruence

Zhumagali Shomanov, Combinatorial formula for the partition function, arXiv:1508.03173 [math.CO] 2015.

T. Sillke, Number of integer partitions

R. P. Stanley, A combinatorial miscellany

Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [math.CO], 2013.

R. L. Weaver, New Congruences for the Partition Function, The Ramanujan Journal 5(1) 2001.

Eric Weisstein's World of Mathematics, Partition, Partition Function P, q-Pochhammer Symbol, and Ramanujan's Identity

West Sussex Grid for Learning, Multicultural Mathematics, Ramanujan's Partition of Numbers

Thomas Wieder, Comment on A000041

Wikipedia, Integer Partition

H. S. Wilf, Lectures on Integer Partitions

Wolfram Research, Generating functions of p(n)

D. J. Wright, Partitions [broken link]

Robert M. Ziff, On Cardy's formula for the critical crossing probability in 2d percolation, J. Phys. A. 28, 1249-1255 (1995).

Index entries for "core" sequences

Index entries for related partition-counting sequences

Index entries for expansions of Product_{k >= 1} (1-x^k)^m

Index entries for sequences related to rooted trees

FORMULA

G.f.: Product_{k>0} 1/(1-x^k) = Sum_{k>= 0} x^k Product_{i = 1..k} 1/(1-x^i) = 1+Sum_{k>0} x^(k^2)/(Product_{i = 1..k} (1-x^i))^2.

G.f.: 1 + Sum_{n>=1} x^n/(Product_{k>=n} 1-x^k). - Joerg Arndt, Jan 29 2011

a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the sign of the k-th term is (-1)^([(k+1)/2]). See A001318 for a good way to remember this!

a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k), where sigma(k) is the sum of divisors of k (A000203).

a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3)) as n -> infinity (Hardy and Ramanujan). See A050811.

From Jon E. Schoenfield, Aug 17 2014: (Start)

It appears that the above approximation from Hardy and Ramanujan can be refined as

a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3 + c0 + c1/n^(1/2) + c2/n + c3/n^(3/2) + c4/n^2 + ...)), where the coefficients c0 through c4 are approximately

     c0 = -0.230420145062453320665537

     c1 = -0.0178416569128570889793

     c2 =  0.0051329911273

     c3 = -0.0011129404

     c4 =  0.0009573,

as n -> infinity. (End)

From Vaclav Kotesovec, May 29 2016: (Start)

c0 = -0.230420145062453320665536704197233... = -1/36 - 2/Pi^2

c1 = -0.017841656912857088979502135349949... = 1/(6*sqrt(6)*Pi) - sqrt(3/2)/Pi^3

c2 =  0.005132991127342167594576391633559... = 1/(2*Pi^4)

c3 = -0.001112940489559760908236602843497... = 3*sqrt(3/2)/(4*Pi^5) - 5/(16*sqrt(6)*Pi^3)

a(n) ~ exp(Pi*sqrt(2*n/3))/(4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi + Pi/(24*sqrt(6)))/sqrt(n) + (1/16 + Pi^2/6912)/n).

a(n) ~ exp(Pi*sqrt(2*n/3) - (sqrt(3/2)/Pi + Pi/(24*sqrt(6)))/sqrt(n) + (1/24 - 3/(4*Pi^2))/n) / (4*sqrt(3)*n).

(End)

a(n) < exp( (2/3)^(1/2) Pi sqrt(n) ) (Ayoub, p. 197).

G.f.: Product (1+x^m)^A001511(m); m=1..inf. - Vladeta Jovovic, Mar 26 2004

a(n) = Sum_{i=0..n-1} P(i, n-i), where P(x, y) is the number of partitions of x into at most y parts and P(0, y)=1. - Jon Perry, Jun 16 2003

G.f.: prod(i>=1, prod(j>=0, (1+x^((2i-1)*2^j))^(j+1))) - Jon Perry, Jun 06 2004

G.f. e^{Sum_{k>0} (x^k/(1-x^k)/k)}. - Franklin T. Adams-Watters, Feb 08 2006

Euler transform of all 1's sequence (A000012). Weighout transform of A001511. - Franklin T. Adams-Watters, Mar 15 2006

a(n) = A027187(n)+A027193(n) = A000701(n)+A046682(n). - Reinhard Zumkeller, Apr 22 2006

Convolved with A152537 gives A000079, powers of 2. - Gary W. Adamson, Dec 06 2008

a(n) = Tr(n)/(24*n-1) = A183011(n)/A183010(n), n>=1. See the Bruinier-Ono paper in the Links. - Omar E. Pol, Jan 23 2011

From Jerome Malenfant, Feb 14 2011: (Start)

a(n) = determinant of the n X n Toeplitz matrix:

   1  -1

   1   1  -1

   0   1   1  -1

   0   0   1   1  -1

  -1   0   0   1   1  -1

   . . .

  d_n  d_(n-1) d_(n-2)...1

where d_q = (-1)^(m+1) if q = m(3m-1)/2 = p_m, the m-th generalized pentagonal number (A001318), otherwise d_q = 0. Note that the 1's run along the diagonal and the -1's are on the superdiagonal. The (n-1) row (not written) would end with ... 1 -1. (End)

Empirical: let F*(x) = Sum_{n=0..infinity} p(n)*exp(-Pi*x*(n+1)), then F*(2/5) = 1/sqrt(5) to a precision of 13 digits.

F*(4/5) = 1/2+3/2/sqrt(5)-sqrt(1/2*(1+3/sqrt(5))) to a precision of 28 digits. These are the only values found for a/b when a/b is from F60, Farey fractions up to 60. The number for F*(4/5) is one of the real roots of 25*x^4 - 50*x^3 - 10*x^2 - 10*x + 1. Note here the exponent (n+1) compared to the standard notation with n starting at 0. - Simon Plouffe, Feb 23 2011

The constant (2^(7/8)*GAMMA(3/4))/(exp(Pi/6)*Pi^(1/4)) = 1.0000034873... when expanded in base exp(4*Pi) will give the first 52 terms of a(n), n>0, the precision needed is 300 decimal digits. - Simon Plouffe, Mar 02 2011

a(n) = A035363(2n). - Omar E. Pol, Nov 20 2009

G.f.: A(x)=1+x/(G(0)-x); G(k)= 1 + x - x^(k+1) - x*(1-x^(k+1))/G(k+1); (continued fraction Euler's kind, 1-step ). - Sergei N. Gladkovskii, Jan 25 2012

Convolution of A010815 with A000712. - Gary W. Adamson, Jul 20 2012

G.f.: 1 + x*(1 - G(0))/(1-x) where G(k) =  1 - 1/(1-x^(k+1))/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 22 2013

G.f.: Q(0) where Q(k) = 1 + x^(4*k+1)/( (x^(2*k+1)-1)^2 - x^(4*k+3)*(x^(2*k+1)-1)^2/( x^(4*k+3) + (x^(2*k+2)-1)^2/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 16 2013

a(n) = 24*spt(n) + 12*N_2(n) - Tr(n) = 24*A092269(n) + 12*A220908(n) - A183011(n), n >= 1. - Omar E. Pol, Feb 17 2013

G.f.: 1/(x; x)_{inf} where (a; q)_k is the q-Pochhammer symbol. - Vladimir Reshetnikov, Apr 24 2013

a(n) = A066186(n)/n, n >= 1. - Omar E. Pol, Aug 16 2013

From Peter Bala, Dec 23 2013: (Start)

a(n-1) = Sum_{parts k in all partitions of n} mu(k), where mu(k) is the arithmetical Möbius function (see A008683).

Let P(2,n) denote the set of partitions of n into parts k >= 2. Then a(n-2) = -Sum_{parts k in all partitions in P(2,n)} mu(k).

n*( a(n) - a(n-1) ) = Sum_{parts k in all partitions in P(2,n)} k (see A138880).

Let P(3,n) denote the set of partitions of n into parts k >= 3. Then

a(n-3) = (1/2)*Sum_{parts k in all partitions in P(3,n)} phi(k), where phi(k) is the Euler totient function (see A000010). Using this result and Merten's theorem on the average order of the phi function, we can find an approximate 3-term recurrence for the partition function:a(n) ~ a(n-1) + a(n-2) + (Pi^2/(3*n) - 1)*a(n-3). For example, substituting the values a(47) = 124,754, a(48) = 147,273 and a(49) = 173,525 into the recurrence gives the approximation a(50) ~ 204,252.48... compared with the true value a(50) = 204,226. (End)

a(n) = Sum_{k=1..n+1} (-1)^(n+1-k)*A000203(k)*A002040(n+1-k). - Mircea Merca, Feb 27 2014

a(n) = A240690(n) + A240690(n+1), n >= 1. - Omar E. Pol, Mar 16 2015

From Gary W. Adamson, Jun 22 2015: (Start)

A production matrix for the sequence with offset 1 is M, an infinite n x n matrix of the following form:

  a, 1, 0, 0, 0, 0,...

  b, 0, 1, 0, 0, 0,...

  c, 0, 0, 1, 0, 0,...

  d, 0, 0, 0, 1, 0,...

.

.

...such that (a, b, c, d,...) is the signed version of A080995 with offset 1: (1,1,0,0,-1,0,-1,...)

and a(n) is the upper left term of M^n.

This operation is equivalent to the g.f. (1 + x + 2x^2 + 3x^3 + 5x^4 + ...) = 1/(1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + ...). (End)

G.f.: x^(1/24)/eta(log(x)/(2 Pi i)). - Thomas Baruchel, Jan 09 2016, after Michael Somos (after Richard Dedekind).

a(n) = Sum_{k=-inf..+inf} (-1)^k a(n-k(3k-1)/2) with a(0)=1 and a(negative)=0. The sum can be restricted to the (finite) range from k = (1-sqrt(1-24n))/6 to (1+sqrt(1-24n))/6), since all terms outside this range are zero. - Jos Koot, Jun 01 2016

G.f.: (conjecture) (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) is A000009: (1, 1, 1, 2, 2, 3, 4,...). - Gary W. Adamson, Sep 18 2016

EXAMPLE

a(5) = 7 because there are seven partitions of 5, namely: {1, 1, 1, 1, 1}, {2, 1, 1, 1}, {2, 2, 1}, {3, 1, 1}, {3, 2}, {4, 1}, {5}. - Bob Selcoe, Jul 08 2014

G.f. = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 11*x^6 + 15*x^7 + 22*x^8 + ...

G.f. = 1/q + q^23 + 2*q^47 + 3*q^71 + 5*q^95 + 7*q^119 + 11*q^143 + 15*q^167 + ...

From Gregory L. Simay, Nov 08 2015: (Start)

There are up to a(4)=5 segmented partitions of the partitions of n with exactly 4 parts. They are a(n,4, <4>), a(n,4,<3,1>), a(n,4,<2,2>), a(n,4,<2,1,1>), a(n,4,<1,1,1,1>).

The partition 8,8,8,8 is counted in a(32,4,<4>).

The partition 9,9,9,5 is counted in a(32,4,<3,1>).

The partition 11,11,5,5 is counted in a(32,4,<2,2>).

The partition 13,13,5,1 is counted in a(32,4,<2,1,1>).

The partition 14,9,6,3 is counted in a(32,4,<1,1,1,1>).

a(n odd,4,<2,2>) = 0.

a(12, 6, <2,2,2>) = a(6,3,<1,1,1>) = a(6-3,3) = a(3,3) = 1. The lone partition is 3,3,2,2,1,1.

(End)

MAPLE

with(combinat); A000041 := numbpart; [ seq(numbpart(i), i=0..50) ]; # Warning: Maple 10 and 11 give incorrect answers in some cases: A110375.

spec := [ B, {B=Set(Set(Z, card>=1))}, unlabeled ]; [seq(combstruct[count](spec, size=n), n=0..50)];

with(combstruct):ZL0:=[S, {S=Set(Cycle(Z, card>0))}, unlabeled]:seq(count(ZL0, size=n), n=0..45); # Zerinvary Lajos, Sep 24 2007

G:={P=Set(Set(Atom, card>0))}:combstruct[gfsolve](G, labeled, x); seq(combstruct[count]([P, G, unlabeled], size=i), i=0..45); # Zerinvary Lajos, Dec 16 2007

MATHEMATICA

Table[ PartitionsP[n], {n, 0, 45}]

a[ n_] := SeriesCoefficient[ q^(1/24) / DedekindEta[ Log[q] / (2 Pi I)], {q, 0, n}]; (* Michael Somos, Jul 11 2011 *)

a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^k, {k, n}], {x, 0, n}]; (* Michael Somos, Jul 11 2011 *)

CoefficientList[1/QPochhammer[q] + O[q]^100, q] (* Jean-François Alcover, Nov 25 2015 *)

PROG

(MAGMA) a:= func< n | NumberOfPartitions(n) >; [ a(n) : n in [0..10]];

(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};

(PARI) /* The Hardy-Ramanujan-Rademacher exact formula in PARI is as follows (this is no longer necessary since it is now built in to the numbpart command): */

Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b); (sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c))

L(n, q) = if(q==1, 1, sum(h=1, q-1, if(gcd(h, q)>1, 0, cos((g(h, q)-2*h*n)*Pi/q))))

g(h, q) = if(q<3, 0, sum(k=1, q-1, k*(frac(h*k/q)-1/2)))

part(n) = round(sum(q=1, max(5, 0.24*sqrt(n)+2), L(n, q)*Psi(n, q)))

/* Ralf Stephan, Nov 30 2002 */

(PARI) {a(n) = numbpart(n)};

(PARI) {a(n) = if( n<0, 0, polcoeff( sum( k=1, sqrtint(n), x^k^2 / prod( i=1, k, 1 - x^i, 1 + x * O(x^n))^2, 1), n))};

(PARI) f(n)= my(v, i, k, s, t); v=vector(n, k, 0); v[n]=2; t=0; while(v[1]<n, i=2; while(v[i]==0, i++); v[i]--; s=sum(k=i, n, k*v[k]); while(i>1, i--; s+=i*(v[i]=(n-s)\i)); t++); t \\ Thomas Baruchel, Nov 07 2005

(PARI) a(n)=if(n<0, 0, polcoeff(exp(sum(k=1, n, x^k/(1-x^k)/k, x*O(x^n))), n)) \\ Joerg Arndt, Apr 16 2010

(Mupad) combinat::partitions::count(i) $i=0..54 // Zerinvary Lajos, Apr 16 2007

(Sage) [number_of_partitions(n) for n in xrange(0, 46)] # Zerinvary Lajos, May 24 2009

(Sage)

@CachedFunction

def A000041(n):

    if n == 0: return 1

    S = 0; J = n-1; k = 2

    while 0 <= J:

        T = A000041(J)

        S = S+T if is_odd(k//2) else S-T

        J -= k if is_odd(k) else k//2

        k += 1

    return S

[A000041(n) for n in (0..49)]  # Peter Luschny, Oct 13 2012

(Haskell)

import Data.MemoCombinators (memo2, integral)

a000041 n = a000041_list !! n

a000041_list = map (p' 1) [0..] where

   p' = memo2 integral integral p

   p _ 0 = 1

   p k m = if m < k then 0 else p' k (m - k) + p' (k + 1) m

-- Reinhard Zumkeller, Nov 03 2015, Nov 04 2013

(Maxima) num_partitions(60, list); /* Emanuele Munarini, Feb 24 2014 */

(GAP) List([1..10], n->Size(OrbitsDomain(SymmetricGroup(IsPermGroup, n), SymmetricGroup(IsPermGroup, n), \^))); # Attila Egri-Nagy, Aug 15 2014

(Perl) use ntheory ":all"; my @p = map { partitions($_) } 0..100; say "[@p]"; # Dana Jacobsen, Sep 06 2015

(Racket)

#lang racket

; SUM(k, -inf, +inf) (-1)^k p(n-k(3k-1)/2)

; For k outside the range (1-(sqrt(1-24n))/6 to (1+sqrt(1-24n))/6) argument n-k(3k-1)/2 < 0.

; Therefore the loops below are finite. The hash avoids repeated identical computations.

(define (p n) ; Nr of partitions of n.

(hash-ref h n

  (λ ()

   (define r

    (+

     (let loop ((k 1) (n (sub1 n)) (s 0))

      (if (< n 0) s

       (loop (add1 k) (- n (* 3 k) 1) (if (odd? k) (+ s (p n)) (- s (p n))))))

     (let loop ((k -1) (n (- n 2)) (s 0))

      (if (< n 0) s

       (loop (sub1 k) (+ n (* 3 k) -2) (if (odd? k) (+ s (p n)) (- s (p n))))))))

   (hash-set! h n r)

   r)))

(define h (make-hash '((0 . 1))))

; (for ((k (in-range 0 50))) (printf "~s, " (p k))) runs in a moment.

; Jos Koot, Jun 01 2016

CROSSREFS

Cf. A000009, A000079, A000203, A001318, A008284, A113685, A132311, A145006, A145007, A147843, A152537, A168532, A173238, A173239, A173241, A173304, A174065, A174066, A174068, A176202.

For successive differences see A002865, A053445, A072380, A081094, A081095.

Antidiagonal sums of triangle A092905. a(n) = A054225(n,0).

Boustrophedon transforms: A000733, A000751.

Cf. A167376 (complement).

KEYWORD

core,easy,nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Ola Veshta (olaveshta(AT)my-deja.com), Feb 28 2001

Additional comments from Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001

STATUS

approved

A000043 Mersenne exponents: primes p such that 2^p - 1 is prime. Then 2^p - 1 is called a Mersenne prime.
(Formerly M0672 N0248) 		+20
495
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Equivalently, integers n such that 2^n - 1 is prime.

It is believed (but unproved) that this sequence is infinite. The data suggest that the number of terms up to exponent N is roughly K log N for some constant K.

Length of prime repunits in base 2.

The associated perfect number N=2^(p-1)*M(p) (=A019279*A000668=A000396), has 2p (=A061645) divisors with harmonic mean p (and geometric mean sqrt(N)). - Lekraj Beedassy, Aug 21 2004

In one of his first publications Euler found the numbers up to 31 but erroneously included 41 and 47.

Equals number of bits in binary expansion of n-th Mersenne prime (A117293). - Artur Jasinski, Feb 09 2007

Number of divisors of n-th even perfect number, divided by 2. Number of divisors of n-th even perfect number that are powers of 2. Number of divisors of n-th even perfect number that are multiples of n-th Mersenne prime A000668(n). - Omar E. Pol, Feb 24 2008

Number of divisors of n-th even superperfect number A061652(n). Numbers of divisors of n-th superperfect number A019279(n), assuming there are no odd superperfect numbers. - Omar E. Pol, Mar 01 2008

Differences between exponents when the even perfect numbers are represented as differences of powers of 2, for example: The 5th even perfect number is 33550336 = 2^25 - 2^12 then a(5)=25-12=13 (see A135655, A133033, A090748). - Omar E. Pol, Mar 01 2008

Number of 1's in binary expansion of n-th even perfect number (see A135650). Number of 1's in binary expansion of divisors of n-th even perfect number that are multiples of n-th Mersenne prime A000668(n) (see A135652, A135653, A135654, A135655). - Omar E. Pol, May 04 2008

Indices of the numbers A006516 that are also even perfect numbers. - Omar E. Pol, Aug 30 2008

Indices of Mersenne numbers A000225 that are also Mersenne primes A000668. - Omar E. Pol, Aug 31 2008

A modification of the Eberhart's conjecture proposed by Wagstaff (1983) which proposes that if q_n is the n-th prime such that M_(q_n) is a Mersenne prime, then q_n is approximately (2^(e^(-gamma)))^n, where gamma is the Euler-Mascheroni constant. [Weisstein, Wagstaff's Conjecture, see link below] - Jonathan Vos Post, Sep 10 2010

The (prime) number p appears in this sequence if and only if there is no prime q<2^p-1 such that the order of 2 modulo q equals p; a special case is that if p=4k+3 is prime and also q=2p+1 is prime then the order of 2 modulo q is p so p is not a term of this sequence. - Joerg Arndt, Jan 16 2011

Primes p such that sigma(2^p) - sigma(2^p-1) = 2^p-1. - Jaroslav Krizek, Aug 02 2013

REFERENCES

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 4.

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.

F. Lemmermeyer, Reciprocity Laws From Euler to Eisenstein, Springer-Verlag, 2000, p. 57.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 19.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

B. Tuckerman, The 24th Mersenne prime, Notices Amer. Math. Soc., 18 (Jun, 1971), Abstract 684-A15, p. 608.

K. Zsigmondy, Zur Theorie der Potenreste, Monatsh. Math., 3 (1892), 265-284.

LINKS

David Wasserman, Table of n, a(n) for n = 1..44 [Updated by N. J. A. Sloane, Feb 06 2013, Alois P. Heinz, May 01 2014, Jan 11 2015]

P. T. Bateman, J. L. Selfridge, S. S. Wagstaff, Jr., The new Mersenne conjecture Amer. Math. Monthly 96 (1989), no. 2, 125--128. MR0992073 (90c:11009).

J. Bernheiden, Mersenne Numbers (Text in German)

Andrew R. Booker, The Nth Prime Page

J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.

P. G. Brown, A Note on Ramanujan's (FALSE) Conjectures Regarding 'Mersenne Primes'

C. K. Caldwell, Mersenne Primes

C. K. Caldwell, Recent Mersenne primes

L. Euler, Observations on a theorem of Fermat and others on looking at prime numbers, arXiv:math/0501118 [math.HO], 2005-2008.

L. Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus

G. Everest et al., Primes generated by recurrence sequences, arXiv:math/0412079 [math.NT], 2006.

G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.

Donald B. Gillies, Three new Mersenne primes and a statistical theory Mathematics of Computation 18.85 (1964): 93-97.

GIMPS (Great Internet Mersenne Prime Search), Distributed Computing Projects

GIMPS, Milestones Report

GIMPS, 48th Known Mersenne Prime Discovered, GIMPS Project Discovers Largest Known Prime Number, 2^57885161 - 1

Wilfrid Keller, List of primes k.2^n - 1 for k < 300

H. Lifchitz, Mersenne and Fermat primes field

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see p. 143.

R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - From N. J. A. Sloane, Jun 13 2012

G. P. Michon, Perfect Numbers, Mersenne Primes

Albert A. Mullin, Letter to the editorabout "The new Mersenne conjecture" [Amer. Math. Monthly 96 (1989), no. 2, 125-128; MR0992073 (90c:11009)] by P. T. Bateman, J. L. Selfridge and S. S. Wagstaff, Jr., Amer. Math. Monthly 96 (1989), no. 6, 511. MR0999415 (90f:11008).

M. Oakes, A new series of Mersenne-like Gaussian primes

Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.

Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]

Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos.

K. Schneider, PlanetMath.org, Mersenne numbers

H. J. Smith, Mersenne Primes

B. Tuckerman, The 24th Mersenne prime, Proc. Nat. Acad. Sci. USA, 68 (1971), 2319-2320.

H. S. Uhler, On All Of Mersenne's Numbers Particularly M_193

H. S. Uhler, First Proof That The Mersenne Number M_157 Is Composite

S. S. Wagstaff, Jr., The Cunningham Project

Eric Weisstein's World of Mathematics, Mersenne Prime

Eric Weisstein's World of Mathematics, Cunningham Number

Eric Weisstein's World of Mathematics, Integer Sequence Primes

Eric Weisstein's World of Mathematics, Repunit

Eric Weisstein's World of Mathematics, Mathworld Headline News, 40th Mersenne Prime Announced

Eric Weisstein's World of Mathematics, Mathworld Headline News, 41st Mersenne Prime Announced

Eric Weisstein, MathWorld Headline News, 42nd Mersenne Prime Found

Eric Weisstein, MathWorld Headline News, 43rd Mersenne Prime Found

Eric Weisstein, MathWorld Headline News, 44th Mersenne Prime Found

Eric Weisstein, MathWorld Headline News, 45th and 46th Mersenne Primes Found - Lekraj Beedassy, Sep 18 2008

Eric Weisstein, MathWorld Headline News, 47th Known Mersenne Prime Apparently Discovered - Lekraj Beedassy, Aug 03 2009

Eric W. Weisstein, Wagstaff's Conjecture, - Jonathan Vos Post, Sep 10 2010

David Whitehouse, Number takes prime position (2^13466917 - 1 found after 13000 years of computer time)

Index entries for sequences of n such that k*2^n-1 (or k*2^n+1) is prime

Index entries for "core" sequences

FORMULA

a(n) = log((1/2)*(1+sqrt(1+8*A000396(n))))/log(2). - Artur Jasinski, Sep 23 2008 (under the assumption there are no odd perfect numbers, Joerg Arndt, Feb 23 2014)

a(n) = A000005(A061652(n)). - Omar E. Pol, Aug 26 2009

a(n) = A000120(A000396(n)), assuming there are no odd perfect numbers. - Omar E. Pol, Oct 30 2013

a(n) = 1 + Sum_{m=1..L(n)}(abs(n-S(m))-abs(n-S(m)-1/2)+1/2), where S(m) = Sum_{k=1..m}(A010051(k)*A010051(2^k-1)) and L(n) >= a(n)-1.  L(n) can be any function of n which satisfies the inequality. - Timothy Hopper, Jun 11 2015.

a(n) = A260073(A000396(n)) + 1, again assuming there are no odd perfect numbers. - Juri-Stepan Gerasimov, Aug 29 2015

a(n) = A050475(n) - 1. - _Mohammed Bouayoun_, Mar 19 2004

EXAMPLE

Corresponding to the initial terms 2, 3, 5, 7, 13, 17, 19, 31 ... we get the Mersenne primes 2^2 - 1 = 3, 2^3 - 1 = 7, 2^5 - 1 = 31, 127, 8191, 131071, 524287, 2147483647 ... (see A000668).

MATHEMATICA

Select[ Prime@ Range@ 1000, PrimeQ[2^# - 1] &] (* Vladimir Joseph Stephan Orlovsky, Apr 29 2008 and modified by Robert G. Wilson v, Jan 20 2014 *)

Flatten[Position[EulerPhi[2^# - 2] + 2 == EulerPhi[2^#]&/@Range[1, 5000], True] - 1] (* Vincenzo Librandi, Aug 31 2015 *)

(* For Mathematica 10.4+ *) Select[Range[10^5], MersennePrimeExponentQ] (* Arkadiusz Wesolowski, Jun 05 2016 *)

PROG

(PARI) isA000043(n) = isprime(2^n-1) \\ Michael B. Porter, Oct 28 2009

(PARI)

LL(e)=

{ /* Lucas-Lehmer test for exponent e */

    local(n, h);

    n = 2^e-1;

    h = Mod(2, n);

    for (k=1, e-2, h=2*h*h-1);

    return( 0==h );

}

forprime(e=2, 5000, if(LL(e), print1(e, ", "))); /* terms<5000, takes 10 secs */

/* Joerg Arndt, Jan 16 2011 */

(PARI) is(n)=my(h=Mod(2, 2^n-1)); for(i=1, n-2, h=2*h^2-1); h==0||n==2 \\ Charles R Greathouse IV, Jun 05 2013

CROSSREFS

See A000668 for the actual primes, A028335 for their lengths.

Cf. A001348, A016027, A046051, A057429, A057951-A057958, A066408, A117293, A127962, A127963, A127964, A127965, A127961, A000979, A000978, A124400, A124401, A127955, A127956, A127957, A127958, A127936, A134458, A000225, A000396, A090748, A133033, A135655, A006516, A019279, A061652, A133033, A135650, A135652, A135653, A135654, A260073, A050475.

KEYWORD

hard,nonn,nice,core

AUTHOR

N. J. A. Sloane

EXTENSIONS

2^6972593 - 1 is known to be the 38th Mersenne prime. - Harry J. Smith, Apr 17 2003

2^13466917 - 1 is known to be the 39th Mersenne prime.

Also in the sequence: p=20996011, for which M(p) is a 6.3 million digit number [Nov 17 2003]. Known to be the 40th Mersenne prime since July 2010. See the GIMPS link for details.

Also in the sequence: p=24036583 (for which M(p) is a 7.2 million digit number) [Jun 01 2004]. Known (double-checked) to be the 41st Mersenne prime since Dec 01 2011. - Jason Kimberley, Jan 05 2012

Also in the sequence: p=25964951 (for which M(p) is a 7.8 million digit number). - Feb 26 2005

Also in the sequence: p=30402457 (for which M(p) is a 9.2 million digit number). - Dec 29 2005

Also in the sequence: p=32582657. - Sep 21 2006

Also in the sequence: p=37156667 and p=43112609. - Sep 15 2008

As of Dec 30 2005 the exhaustive search been run through 16693000, according to the GIMPS status page (thanks to R. K. Guy for this information). - N. J. A. Sloane, Dec 30 2005

Also in the sequence: p=42643801 (April 2009).

Also in the sequence: p=57885161 (Jan 25 2013).

Added 30402457, now known to be a(43), Joerg Arndt, Mar 04 2014

Added a(44), verified by GIMPS [via Tony Noe], by Charles R Greathouse IV, Nov 10 2014

Also in the sequence: p=74207281. - Charles R Greathouse IV, Jan 19 2016

STATUS

approved

A008578 Prime numbers at the beginning of the 20th century (today 1 is no longer regarded as a prime). +20
277
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

1 together with the primes; also called the noncomposite numbers.

Also largest sequence of nonnegative integers with the property that the product of 2 or more elements with different indices is never a square. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001 [Comment corrected by Farideh Firoozbakht, Aug 03 2014]

Numbers n such that their largest divisor <= sqrt(n) equals 1. (See also A161344, A161345, A161424). - Omar E. Pol, Jul 05 2009

Or numbers n with only perfect partition A002033;  1 together with the prime numbers A000040. - Juri-Stepan Gerasimov, Sep 27 2009

Numbers n such that d(n) < 3. - Juri-Stepan Gerasimov, Oct 17 2009

Also first column of array in A163280. Also first row of array in A163990. - Omar E. Pol, Oct 24 2009

a(n) = possible values of A136548(m) in increasing order, where A136548(m) = the largest numbers h such that A000203(h) <= k (k = 1,2,3,..), where A000203(h) = sum of divisors of h. - Jaroslav Krizek, Mar 01 2010

Where record values of A022404 occur: A086332(n)=A022404(a(n)). - Reinhard Zumkeller, Jun 21 2010

a(n) = A181363((2*n-1)*2^k), k >= 0. - Reinhard Zumkeller, Oct 16 2010

Positive integers that have no divisors other than 1 and itself (the old definition of prime numbers). - Omar E. Pol, Aug 10 2012

Conjecture: the sequence contains exactly those n such that sigma(n) > n*BigOmega(n). - Irina Gerasimova, Jun 08 2013

Note on the Gerasimova conjecture: all members in the sequence obviously satisfy the inequality, because sigma(p) = 1+p and BigOmega(p) = 1 for primes p, so 1+p > p*1. For composites, the (opposite) inequality is heuristically correct at least up to n <= 4400000. The general proof requires to show that BigOmega(n) is an upper limit of the abundancy sigma(n)/n for composite n. This proof is easy for semiprimes n=p1*p2 in general, where sigma(n)=1+p1+p2+p1*p2 and BigOmega(n)=2 and p1, p2 <= 2. - R. J. Mathar, Jun 12 2013

Numbers n such that phi(n)+sigma(n)=2n. - Farideh Firoozbakht, Aug 03 2014

REFERENCES

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.

G. Chrystal, Algebra: An Elementary Textbook. Chelsea Publishing Company, 7th edition, (1964), chap. III.7, p. 38.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 11.

H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035

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. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.

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

Williams, H. C.; Shallit, J. O. 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

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]

Chris K. Caldwell, Angela Reddick, Yeng Xiong and Wilfrid Keller, The History of the Primality of One: A Selection of Sources, (a dynamic survey), Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.

C. K. Caldwell and Y. Xiong, What is the smallest prime?, arXiv preprint arXiv:1209.2007, 2012. - From N. J. A. Sloane, Dec 26 2012

G. P. Michon, Is 1 a prime number?

Omar E. Pol, Illustration of initial terms

Omar E. Pol, Illustration of initial terms of A008578, A161344, A161345, A161424

PrimeFan, Arguments for and against the primality of 1

A. Reddick and Y. Xiong, The search for one as a prime number: from ancient Greece to modern times, Electronic Journal of Undergraduate Mathematics, Volume 16, 1 { 13, 2012. - From N. J. A. Sloane, Feb 03 2013

J. Todd, Review of Lehmer's tables, Mathematical Tables and Other Aids..,  Vol. 11, No. 60, (1957) (on JSTOR.org).

Wikipedia, Complete sequence.

Wikipedia, Dirichlet convolution

FORMULA

m is in the sequence iff sigma(m)+phi(m)=2m. - Farideh Firoozbakht, Jan 27 2005

a(n) = A158611(n+1) for n >= 1. - Jaroslav Krizek, Jun 19 2009

In the following formulas (based on emails from Jaroslav Krizek and R. J. Mathar), the star denotes a Dirichlet convolution between two sequences, and "This" is A008578.

This = A030014 * A008683. (Dirichlet convolution using offset 1 with A030014)

This = A030013 * A000012. (Dirichlet convolution using offset 1 with A030013)

This = A034773 * A007427. (Dirichlet convolution)

This = A034760 * A023900. (Dirichlet convolution)

This = A034762 * A046692. (Dirichlet convolution)

This * A000012 = A030014. (Dirichlet convolution using offset 1 with A030014)

This * A008683 = A030013. (Dirichlet convolution using offset 1 with A030013)

This * A000005 = A034773. (Dirichlet convolution)

This * A000010 = A034760. (Dirichlet convolution)

This * A000203 = A034762. (Dirichlet convolution)

A002033(a(n))=1. - Juri-Stepan Gerasimov, Sep 27 2009

A033273(a(n))=1. - Juri-Stepan Gerasimov, Dec 07 2009

a(n) = A001747(n)/2. - Omar E. Pol, Jan 30 2012

A060448(a(n)) = 1. - Reinhard Zumkeller, Apr 05 2012

A086971(a(n)) = 0. - Reinhard Zumkeller, Dec 14 2012

Sum_{n>=1} x^a(n) = (sum_{n>=1} (A002815(n)*x^n))*(1-x)^2. - L. Edson Jeffery, Nov 25 2013

MAPLE

A008578 := n->if n=1 then 1 else ithprime(n-1); fi :

MATHEMATICA

Join[ {1}, Table[ Prime[n], {n, 1, 60} ] ]

NestList[ NextPrime, 1, 57] (* Robert G. Wilson v, Jul 21 2015 *)

PROG

(PARI) is(n)=isprime(n)||n==1

(MAGMA) [1] cat [n: n in PrimesUpTo(271)];  // Bruno Berselli, Mar 05 2011

(Haskell)

a008578 n = a008578_list !! (n-1)

a008578_list = 1 : a000040_list

-- Reinhard Zumkeller, Nov 09 2011

CROSSREFS

The main entry for this sequence is A000040.

The complement of A002808.

Cf. A000732 (boustrophedon transform).

Cf. A000010, A000203.

Cf. A023626 (self-convolution).

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

A002385 Palindromic primes: prime numbers whose decimal expansion is a palindrome.
(Formerly M0670 N0247) 		+20
189
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Every palindrome with an even number of digits is divisible by 11, so 11 is the only member of the sequence with an even number of digits. - David Wasserman, Sep 09 2004

This holds in any number base A006093(n), n>1. - Lekraj Beedassy, Mar 07 2005

The log-log plot shows the fairly regular structure of these numbers. - T. D. Noe, Jul 09 2013

Conjecture: The only primes with palindromic prime indices that are palindromic primes themselves are 3, 5 and 11. Tested for the primes with the first 8000000 palindromic prime indices. - Ivan N. Ianakiev, Oct 10 2014

REFERENCES

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 228.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..47995 (all primes with fewer than 12 digits), Oct 14 2015, extending earlier b-files from T. D. Noe and A. Olah.

K. S. Brown, On General Palindromic Numbers

C. K. Caldwell, "Top Twenty" page, Palindrome

P. De Geest, World!Of Palindromic Primes

T. D. Noe, Log-log plot of the first 401696 terms

I. Peterson, Math Trek, Palindromic Primes

M. Shafer, First 401066 Palprimes [Broken link]

Eric Weisstein's World of Mathematics, Palindromic Number

Eric Weisstein's World of Mathematics, Palindromic Prime

Eric Weisstein's World of Mathematics, Integer Sequence Primes

Wikipedia, Palindromic prime

Index entries for sequences related to palindromes

FORMULA

Intersection of A000040 (primes) and A002113 (palindromes).

A010051(a(n)) * A136522(a(n)) = 1. [Reinhard Zumkeller, Apr 11 2011]

MAPLE

ff := proc(n) local i, j, k, s, aa, nn, bb, flag; s := n; aa := convert(s, string); nn := length(aa); bb := ``; for i from nn by -1 to 1 do bb := cat(bb, substring(aa, i..i)); od; flag := 0; for j from 1 to nn do if substring(aa, j..j)<>substring(bb, j..j) then flag := 1 fi; od; RETURN(flag); end; gg := proc(i) if ff(ithprime(i)) = 0 then RETURN(ithprime(i)) fi end;

rev:=proc(n) local nn, nnn: nn:=convert(n, base, 10): add(nn[nops(nn)+1-j]*10^(j-1), j=1..nops(nn)) end: a:=proc(n) if n=rev(n) and isprime(n)=true then n else fi end: seq(a(n), n=1..20000); # rev is a Maple program to revert a number - Emeric Deutsch, Mar 25 2007

# A002385 Gets all base-10 palindromic primes with exactly d digits, in the list "Res"

d:=7; # (say)

if d=1 then Res:= [2, 3, 5, 7]:

elif d=2 then Res:= [11]:

elif d::even then

    Res:=[]:

else

    m:= (d-1)/2:

    Res2 := [seq(seq(n*10^(m+1)+y*10^m+digrev(n), y=0..9), n=10^(m-1)..10^m-1)]:

    Res:=[]: for x in Res2 do if isprime(x) then Res:=[op(Res), x]; fi: od:

fi:

Res; # N. J. A. Sloane, Oct 18 2015

MATHEMATICA

Select[ Prime[ Range[2100] ], IntegerDigits[#] == Reverse[ IntegerDigits[#] ] & ]

lst = {}; e = 3; Do[p = n*10^(IntegerLength[n] - 1) + FromDigits@Rest@Reverse@IntegerDigits[n]; If[PrimeQ[p], AppendTo[lst, p]], {n, 10^e - 1}]; Insert[lst, 11, 5] (* Arkadiusz Wesolowski, May 04 2012 *)

Join[{2, 3, 5, 7, 11}, Flatten[Table[Select[Prime[Range[PrimePi[ 10^(2n)]+1, PrimePi[ 10^(2n+1)]]], # == IntegerReverse[#]&], {n, 3}]]] (* The program uses the IntegerReverse function from Mathematica version 10 *) (* Harvey P. Dale, Apr 22 2016 *)

PROG

(Haskell)

a002385 n = a002385_list !! (n-1)

a002385_list = filter ((== 1) . a136522) a000040_list

-- Reinhard Zumkeller, Apr 11 2011

(PARI) is(n)=n==eval(concat(Vecrev(Str(n))))&&isprime(n) \\ Charles R Greathouse IV, Nov 20 2012

(PARI) forprime(p=2, 10^5, my(d=digits(p, 10)); if(d==Vecrev(d), print1(p, ", "))); \\ Joerg Arndt, Aug 17 2014

(Python)

from itertools import chain

from sympy import isprime

A002385 = sorted((n for n in chain((int(str(x)+str(x)[::-1]) for x in range(1, 10**5)), (int(str(x)+str(x)[-2::-1]) for x in range(1, 10**5))) if isprime(n))) # Chai Wah Wu, Aug 16 2014

CROSSREFS

A007500 = this sequence union A006567.

Subsequence of A188650; A188649(a(n)) = a(n); see A033620 for multiplicative closure. [Reinhard Zumkeller, Apr 11 2011]

Cf. A016041, A029732, A117697.

KEYWORD

nonn,base,nice,easy

AUTHOR

N. J. A. Sloane, Simon Plouffe

EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Oct 25 2000

Comment from A006093 moved here by Franklin T. Adams-Watters, Dec 03 2009

Mentioned the sequence A006093 in my comment, previously omitted by mistake Lekraj Beedassy, Dec 06 2009

STATUS

approved

A233862 Prime(n), where n is such that (1+sum_{i=1..n} prime(i)^2) / n is an integer. +20
91
2, 3, 5, 7, 13, 23, 37, 41, 101, 107, 197, 317, 1033, 2029, 2357, 2473, 2879, 5987, 6173, 35437, 56369, 81769, 195691, 199457, 793187, 850027, 1062931, 1840453, 2998421, 4217771, 6200923, 9914351, 10153807, 13563889, 18878099, 60767923, 118825361, 170244929 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

a(51) > 1428199016921.

LINKS

Robert Price, Table of n, a(n) for n = 1..50

OEIS Wiki, Sums of powers of primes divisibility sequences

EXAMPLE

a(5) = 13, because 13 is the 6th prime and the sum of the first 6 primes^2+1 = 378 when divided by 6 equals 63 which is an integer.

MATHEMATICA

t = {}; sm = 1; Do[sm = sm + Prime[n]^2; If[Mod[sm, n] == 0, AppendTo[t, Prime[n]]], {n, 100000}]; t (* Derived from A217599 *)

Module[{nn=9600000}, Prime[#]&/@Transpose[Select[Thread[{Range[nn], 1+ Accumulate[ Prime[Range[nn]]^2]}], IntegerQ[Last[#]/First[#]]&]][[1]]] (* Harvey P. Dale, Sep 09 2014 *)

PROG

(PARI) is(n)=if(!isprime(n), return(0)); my(t=primepi(n), s); forprime(p=2, n, s+=Mod(p, t)^2); s==0 \\ Charles R Greathouse IV, Nov 30 2013

CROSSREFS

Cf. A085450 = smallest m > 1 such that m divides Sum_{k=1..m} prime(k)^n.

Cf. A007504, A045345, A171399, A128165, A233523, A050247, A050248.

Cf. A024450, A111441, A217599, A128166, A233862, A217600, A217601.

KEYWORD

nonn

AUTHOR

Robert Price, Dec 16 2013

STATUS

approved

A019546 Primes whose digits are primes. +20
90
2, 3, 5, 7, 23, 37, 53, 73, 223, 227, 233, 257, 277, 337, 353, 373, 523, 557, 577, 727, 733, 757, 773, 2237, 2273, 2333, 2357, 2377, 2557, 2753, 2777, 3253, 3257, 3323, 3373, 3527, 3533, 3557, 3727, 3733, 5227, 5233, 5237, 5273, 5323, 5333, 5527, 5557 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Intersection of A046034 and A000040; A055642(a(n)) = A193238(a(n)). - Reinhard Zumkeller, Jul 19 2011

Ribenboim mentioned in 2000 the following number as largest known term: 72323252323272325252 * (10^3120 - 1) / (10^20 - 1) + 1. It has 3120 digits, and was discovered by Harvey Dubner in 1992. Larger terms are 22557252272*R(15600)/R(10) and 2255737522*R(15600) where R(n) denotes the n-th repunit (see A002275): Both have 15600 digits and were found in 2002, also by Dubner (see Weisstein link). David Broadhurst reports in 2003 an even longer number with 82000 digits: (10^40950+1) * (10^20055+1) * (10^10374 + 1) * (10^4955 + 1) * (10^2507 + 1) * (10^1261 + 1) * (3*R(1898) + 555531001*10^940 - R(958)) + 1, see link. - Reinhard Zumkeller, Jan 13 2012

REFERENCES

H. Ibstedt, A Few Smarandache Integer Sequences, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, pp. 171-183.

Paulo Ribenboim, Prime Number Records (Chap 3), in 'My Numbers, My Friends', Springer-Verlag 2000 NY, page 76.

Sylvester Smith, "A Set of Conjectures on Smarandache Sequences", Bulletin of Pure and Applied Sciences, (Bombay, India), Vol. 15 E (No. 1), 1996, pp. 101-107.

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

David Broadhurst: primeform, 82000-digit prime with all digits prime

Chris K. Caldwell, The Prime Glossary: Prime-digit prime

Eric Weisstein's MathWorld Headline News, Two Gigantic Primes with Prime Digits Found

Eric Weisstein's World of Mathematics, Smarandache Sequences

MATHEMATICA

Select[Prime[Range[700]], Complement[IntegerDigits[#], {2, 3, 5, 7}] == {} &] (* Alonso del Arte, Aug 27 2012 *)

PROG

(PARI) primedigits(n) = { local(ln, x, flag, j, y); forprime(x=2, n, ln=length(Str(x)); y=Vec(Str(x)); flag=0; for(j=1, ln, if(isprime(eval(y[j])), flag=1, flag=0; break) ); if(flag, print1(x", ") ) ) } \\ Cino Hilliard, Aug 06 2006

(PARI) is_A019546(n)=isprime(n) & !setminus(Set(Vec(Str(n))), Vec("2357")) \\ M. F. Hasler, Jan 13 2012

(PARI) print1(2); for(d=1, 4, forstep(i=1, 4^d-1, [1, 1, 2], p=sum(j=0, d-1, 10^j*[2, 3, 5, 7][(i>>(2*j))%4+1]); if(isprime(p), print1(", "p)))) \\ Charles R Greathouse IV, Apr 29 2015

(Haskell)

a019546 n = a019546_list !! (n-1)

a019546_list = filter (all (`elem` "2357") . show )

                      ([2, 3, 5] ++ (drop 2 a003631_list))

-- Or, much more efficient:

a019546_list = filter ((== 1) . a010051) $

                      [2, 3, 5, 7] ++ h ["3", "7"] where

   h xs = (map read xs') ++ h xs' where

     xs' = concat $ map (f xs) "2357"

     f xs d = map (d :) xs

-- Reinhard Zumkeller, Jul 19 2011

(MAGMA) [p: p in PrimesUpTo(5600) | Set(Intseq(p)) subset [2, 3, 5, 7]]; // Bruno Berselli, Jan 13 2012

CROSSREFS

Cf. A045336, A003631, A034844, A179336, A109066, A215927.

KEYWORD

nonn,base

AUTHOR

R. Muller

EXTENSIONS

More terms from Cino Hilliard, Aug 06 2006

Thanks to Charles R Greathouse IV and T. D. Noe for massive editing support.

STATUS

approved

A046034 Numbers whose digits are primes. +20
90
2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77, 222, 223, 225, 227, 232, 233, 235, 237, 252, 253, 255, 257, 272, 273, 275, 277, 322, 323, 325, 327, 332, 333, 335, 337, 352, 353, 355, 357, 372, 373, 375, 377, 522, 523, 525, 527, 532 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

A055642(a(n)) = A193238(a(n)). - Reinhard Zumkeller, Jul 19 2011

If n is represented as a zerofree base-4 number (s. A084544) according to n=d(m)d(m-1)...d(3)d(2)d(1)d(0) then a(n)= sum_{j=0..m} c(d(j))*10^j, where c(k)=2,3,5,7 for k=1..4. - Hieronymus Fischer, May 30 2012

According to A153025, it seems that 5, 235 and 72335 are the only terms whose square is again a term, i.e., which are also in the sequence A275971 of square roots of the terms which are squares, listed in A191486. - M. F. Hasler, Sep 16 2016

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Smarandache Sequences.

FORMULA

From Hieronymus Fischer, Apr 20, May 30 and Jun 25 2012: (Start)

a(n) = sum_{j=0..m-1} ((2*b(j)+1) mod 8 + floor(b(j)/4) - floor((b(j)-1)/4))*10^j, where m = floor(log_4(3*n+1)), b(j) = floor((3*n+1-4^m)/(3*4^j)).

Also: a(n) = sum_{j=0..m-1} (A010877(A005408(b(j)) + A002265(b(j)) - A002265(b(j)-1))*10^j.

Special values:

a(1*(4^n-1)/3) = 2*(10^n-1)/9.

a(2*(4^n-1)/3) = 1*(10^n-1)/3.

a(3*(4^n-1)/3) = 5*(10^n-1)/9.

a(4*(4^n-1)/3) = 7*(10^n-1)/9.

Inequalities:

a(n) <= 2*(10^log_4(3*n+1)-1)/9, equality holds for n = (4^k-1)/3, k>0.

a(n) <= 2*A084544(n), equality holds iff all digits of A084544(n) are 1.

a(n) > A084544(n).

Lower and upper limits:

lim inf a(n)/10^log_4(n) = 7/90*10^log_4(3) = 0.482321677069870, for n --> inf.

lim sup a(n)/10^log_4(n) = 2/9*10^log_4(3) = 1.37806193448534318470, for n --> inf.

where 10^log_4(n) = n^1.66096404744...

G.f.: g(x) = (x^(1/3)*(1-x))^(-1) sum_{j=>0} 10^j*z(j)^(4/3)*(2 + z(j) + 2*z(j)^2 + 2*z(j)^3 - 7*z(j)^4)/(1-z(j)^4), where z(j) = x^4^j.

Also g(x) = (x^(1/3)*(1-x))^(-1) sum_{j>=0} 10^j*z(j)^(4/3)*(1-z(j))*(2 + 3z(j) + 5*z(j)^2 + 7*z(j)^3)/(1-z(j)^4), where z(j)=x^4^j.

Also: g(x) = (1/(1-x))*(2*h_(4,0)(x) + h_(4,1)(x) + 2*h_(4,2)(x) + 2*h_(4,3)(x) - 7*h_(4,4)(x)), where h_(4,k)(x) = sum_{j>=0} 10^j*x^((4^(j+1)-1)/3)*x^(k*4^j)/(1-x^4^(j+1)).

(End)

EXAMPLE

a(100)   = 2277,

a(10^3)  = 55327,

a(9881)  = 3233232,

a(10^4)  = 3235757,

a(10922) = 3333333,

a(10^5)  = 227233257.

MATHEMATICA

Table[FromDigits /@ Tuples[{2, 3, 5, 7}, n], {n, 3}] // Flatten (* Michael De Vlieger, Sep 19 2016 *)

PROG

(PARI) primedigits(n) = { local(ln, x, flag, j, y); for(x=2, n, ln=length(Str(x)); y=Vec(Str(x)); flag=0; for(j=1, ln, if(isprime(eval(y[j])), flag=1, flag=0; break) ); if(flag, print1(x", ") ) ) } - Cino Hilliard, Aug 06 2006

(PARI) is_A046034(n)=Set(isprime(digits(n)))==[1] \\ Works at least in PARI v. >= 2.6. - M. F. Hasler, Oct 12 2013

(Haskell)

a046034 n = a046034_list !! (n-1)

a046034_list = filter (all (`elem` "2357") . show ) [0..]

-- Reinhard Zumkeller, Jul 19 2011

(MAGMA) [n: n in [2..532] | Set(Intseq(n)) subset [2, 3, 5, 7]];  // Bruno Berselli, Jul 19 2011

CROSSREFS

Cf. A046035, A118950, A019546 (primes), A203263, A035232, A039996, A085823, A052382, A084544, A084984, A017042, A001743, A001744, A014261, A014263, A193238, A202267, A202268, A211681.

KEYWORD

nonn,base,easy

AUTHOR

Eric W. Weisstein

EXTENSIONS

More terms from Cino Hilliard, Aug 06 2006

Typo in second formula corrected by Hieronymus Fischer, May 12 2012

Two typos in example section corrected by Hieronymus Fischer, May 30 2012

STATUS

approved

A002379 Floor(3^n/2^n).
(Formerly M0666 N0245) 		+20
83
1, 1, 2, 3, 5, 7, 11, 17, 25, 38, 57, 86, 129, 194, 291, 437, 656, 985, 1477, 2216, 3325, 4987, 7481, 11222, 16834, 25251, 37876, 56815, 85222, 127834, 191751, 287626, 431439, 647159, 970739, 1456109, 2184164, 3276246, 4914369, 7371554, 11057332 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

It is an important unsolved problem related to Waring's problem to show that a(n) = floor((3^n-1)/(2^n-1)) holds for all n > 1. This has been checked for 10000 terms and is true for all sufficiently large n, by a theorem of Mahler. [Lichiardopol]

a(n) = floor((3^n-1)/(2^n-1)) holds true at least for 2<=n<=305000. - Hieronymus Fischer, Dec 31 2008

a(n) is also the curve length (rounded down) of the Sierpiński arrowhead curve after n iterations, let a(0) = 1. - Kival Ngaokrajang, May 21 2014

REFERENCES

D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 82.

S. S. Pillai, On Waring's problem, J. Indian Math. Soc., 2 (1936), 16-44.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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 = 0..1000

R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20.

N. Lichiardopol, Problem 925 (BCC20.19), A number-theoretic problem, in Research Problems from the 20th British Combinatorial Conference, Discrete Math., 308 (2008), 621-630.

K. Mahler, On the fractional parts of the powers of a rational number, II, Mathematika 4 (1957), 122-124.

Kival Ngaokrajang, Illustration of Sierpinski arrowhead curve for n = 0..5

Eric Weisstein's World of Mathematics, Power Floors

Wikipedia, Sierpiński arrowhead curve

FORMULA

a(n) = b(n)-(-2/3)^n where b(n) is defined by the recursion b(0):=2, b(1):=5/6, b(n+1):=(5/6)*b(n)+b(n-1). - Hieronymus Fischer, Dec 31 2008

a(n) = (1/2)*(b(n)+sqrt(b(n)^2-(-4)^n)) (with b(n) as defined above). - Hieronymus Fischer, Dec 31 2008

3^n = a(n)*2^n+ A002380(n). - R. J. Mathar, Oct 26 2012

MAPLE

A002379:=n->floor(3^n/2^n); seq(A002379(k), k=0..100); # Wesley Ivan Hurt, Oct 29 2013

MATHEMATICA

Table[Floor[(3/2)^n], {n, 0, 40}] (* Robert G. Wilson v *)

PROG

(PARI) a(n)=3^n>>n \\ Charles R Greathouse IV, Jun 10 2011

(MAGMA) [Floor(3^n / 2^n): n in [0..40]]; // Vincenzo Librandi, Sep 08 2011

(Maxima) makelist(floor(3^n/2^n), n, 0, 50); /* Martin Ettl, Oct 17 2012 */

(Haskell)

a002379 n = 3^n `div` 2^n  -- Reinhard Zumkeller, Jul 11 2014

CROSSREFS

Cf. A094969-A094500, A000217, A081464, A153662, A153665, A153666.

Cf. A060692, A002380, A000079, A000244.

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Apr 30 1991

EXTENSIONS

More terms from Robert G. Wilson v, May 11 2004

First comment starting value corrected by Fred Daniel Kline, Nov 09 2013

STATUS

approved

A112088 Number of leaf nodes in a binary tree. +20
77
2, 3, 5, 7, 11, 16, 24, 36, 54, 81, 122, 183, 274, 411, 617, 925, 1388, 2082, 3123, 4684, 7026, 10539, 15809, 23713, 35570, 53355, 80032, 120048, 180072, 270108, 405162, 607743, 911615, 1367422, 2051133, 3076700, 4615050, 6922575, 10383862 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

LINKS

David W. Wilson, Table of n, a(n) for n=1..1000

Simon Strandgaard, About this sequence

FORMULA

a(1)=2; a(n)=floor((5+sum(a(1) to a(n-1)))/2) - Graeme McRae, Jun 09 2006

MATHEMATICA

f[n_] := Block[{a = 2, b = 0, c = 4}, Do[x = b + a; c -= x; If[c < 0, a *= 2; c += 2a]; b = Floor[(2a - c + 1)/2], {i, n}]; x]; Array[f, 40] (* Robert G. Wilson v, Jan 11 2006 *))

f[s_] := Append[s, Ceiling[2 + Plus @@ s/2]]; Nest[f, {2}, 38] (* Robert G. Wilson v, Jul 08 2006 *)

PROG

(Ruby) a, c=2, 4; p Array.new(99){c-=x=(a*4-c+1)/2; c+=2*a*=2 if c<0; x}

a:=2; b:=0; c:=4; p := proc() local x; global a, b, c; x := b + a; c := c - x; if(c<0) then a := a*2; c := c + a*2; end if; b := floor((a*2-c+1) / 2); x end proc: seq(p(), i=0..40);

KEYWORD

easy,nonn

AUTHOR

Simon Strandgaard (neoneye(AT)gmail.com), Nov 29 2005

STATUS

approved

page 1 2 3 4 5 6 7 8 9 10 ... 240

Search completed in 12.979 seconds

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

License Agreements, Terms of Use, Privacy Policy .

Last modified October 18 08:11 EDT 2016. Contains 277032 sequences.