login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000607 Number of partitions of n into prime parts.
(Formerly M0265 N0093)
164
1, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 30, 35, 40, 46, 52, 60, 67, 77, 87, 98, 111, 124, 140, 157, 175, 197, 219, 244, 272, 302, 336, 372, 413, 456, 504, 557, 614, 677, 744, 819, 899, 987, 1083, 1186, 1298, 1420, 1552, 1695, 1850, 2018, 2198, 2394, 2605, 2833, 3079, 3344 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

a(n) gives the number of values of k such that A001414(k) = n. - Howard A. Landman, Sep 25 2001

Let W(n) = {prime p: There is at least one number m whose spf is p, and sopfr(m) = n}. Let V(n,p) = {m: sopfr(m) = n, p belongs to W(n)}. Then a(n) = sigma(|V(n,p)|). E.g.: W(10) = {2,3,5}, V(10,2) = {30,32,36}, V(10,3) = {21}, V(10,5) = {25}, so a(10) = 3+1+1 = 5. - David James Sycamore, Apr 14 2018

From Gus Wiseman, Jan 18 2020: (Start)

Also the number of integer partitions such that the sum of primes indexed by the parts is n. For example, the sum of primes indexed by the parts of the partition (3,2,1,1) is prime(3)+prime(2)+prime(1)+prime(1) = 12, so (3,2,1,1) is counted under a(12). The a(2) = 1 through a(14) = 10 partitions are:

1 2 11 3 22 4 32 41 33 5 43 6 44

21 111 31 221 222 42 322 331 51 52

211 1111 311 321 411 421 332 431

2111 2211 2221 2222 422 3222

11111 3111 3211 3221 3311

21111 22111 4111 4211

111111 22211 22221

31111 32111

211111 221111

1111111

(End)

REFERENCES

R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; see p. 203.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).

B. C. Berndt and B. M. Wilson, Chapter 5 of Ramanujan's second notebook, pp. 49-78 of Analytic Number Theory (Philadelphia, 1980), Lect. Notes Math. 899, 1981, see Entry 29.

D. M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002.

L. M. Chawla and S. A. Shad, On a trio-set of partition functions and their tables, J. Natural Sciences and Mathematics, 9 (1969), 87-96.

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, Vaclav Kotesovec and H. Havermann, Table of n, a(n) for n = 0..50000 (first 1000 terms from T. D. Noe, terms 1001-20000 from Vaclav Kotesovec, terms 20001-50000 extracted from files by H. Havermann)

K. Alladi and P. Erdős, On an additive arithmetic function, Pacific J. Math., Volume 71, Number 2 (1977), 275-294.

George E. Andrews, Arnold Knopfmacher, John Knopfmacher, Engel expansions and the Rogers-Ramanujan identities J. Number Theory 80 (2000), 273-290. See Eq. 2.1.

George E. Andrews, Arnold Knopfmacher, and Burkhard Zimmermann, On the Number of Distinct Multinomial Coefficients, Journal of Number Theory, Volume 118, Issue 1, May 2006, Pages 15-30.

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.

Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.

Johann Bartel, R. K. Bhaduri, Matthias Brack, and M. V. N. Murthy, Asymptotic prime partitions of integers, Phys. Rev. E, 95 (2017), 052108, arXiv:1609.06497 [math-ph], 2016-2017.

P. T. Bateman, P. Erdős, Partitions into primes, Publ. Math. Debrecen 4 (1956), 198--200.

J. Browkin, Sur les décompositions des nombres naturels en sommes de nombres premiers, Colloquium Mathematicum 5 (1958), 205-207.

Edward A. Bender, Asymptotic methods in enumeration, SIAM Review 16 (1974), no. 4, p. 509.

L. M. Chawla and S. A. Shad, Review of "On a trio-set of partition functions and their tables", Mathematics of Computation, Vol. 24, No. 110 (Apr., 1970), pp. 490-491.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see Section VIII.6, pp. 576ff.

H. Gupta, Partitions into distinct primes, Proc. Nat. Acad. Sci. India, 21 (1955), 185-187.

O. P. Gupta and S. Luthra, Partitions into primes, Proc. Nat. Inst. Sci. India. Part A. 21 (1955), 181-184.

R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy)

R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

H. Havermann, Tables of sum-of-prime-factors sequences (including sequence lengths, i.e. number of prime-parts partitions, for the first 50000).

BongJu Kim, Partition number identities which are true for all set of parts, arXiv:1803.08095 [math.CO], 2018.

Vaclav Kotesovec, Graph - asymptotic ratio for log(a(n)), without minor asymptotic term

Vaclav Kotesovec, Wrong asymptotics of OEIS A000607? (MathOverflow). Includes discussion of the contradiction between the results for the next-to-leading term in the asymptotic formulas by Vaughan and by Bartel et al.

John F. Loase (splurge(AT)aol.com), David Lansing, Cassie Hryczaniuk and Jamie Cahoon, A Variant of the Partition Function, College Mathematics Journal, Vol. 36, No. 4 (Sep 2005), pp. 320-321.

Ljuben Mutafchiev, A Note on Goldbach Partitions of Large Even Integers, arXiv:1407.4688 [math.NT], 2014-2015.

Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.

N. J. A. Sloane, Transforms

R. C. Vaughan, On the number of partitions into primes, Ramanujan J. vol. 15, no. 1 (2008) 109-121.

Eric Weisstein's World of Mathematics, Prime Partition.

Roger Woodford, Bounds for the Eventual Positivity of Difference Functions of Partitions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.3.

Index entries for sequences related to Goldbach conjecture

FORMULA

Asymptotically a(n) ~ exp(2 Pi sqrt(n/log n) / sqrt(3)) (Ayoub).

a(n) = (1/n)*Sum_{k=1..n} A008472(k)*a(n-k). - Vladeta Jovovic, Aug 27 2002

G.f.: 1/Product_{k>=1} (1-x^prime(k)).

See the partition arrays A116864 and A116865.

From Vaclav Kotesovec, Sep 15 2014 [Corrected by Andrey Zabolotskiy, May 26 2017]: (Start)

It is surprising that the ratio of the formula for log(a(n)) to the approximation 2 * Pi * sqrt(n/(3*log(n))) exceeds 1. For n=20000 the ratio is 1.00953, and for n=50000 (using the value from Havermann's tables) the ratio is 1.02458, so the ratio is increasing. See graph above.

A more refined asymptotic formula is found by Vaughan in Ramanujan J. 15 (2008), pp. 109-121, and corrected by Bartel et al. (2017): log(a(n)) = 2*Pi*sqrt(n/(3*log(n))) * (1 - log(log(n))/(2*log(n)) + O(1/log(n))).

See Bartel, Bhaduri, Brack, Murthy (2017) for a more complete asymptotic expansion. (End)

G.f.: 1 + Sum_{i>=1} x^prime(i) / Product_{j=1..i} (1 - x^prime(j)). - Ilya Gutkovskiy, May 07 2017

a(n) = A184198(n) + A184199(n). - Vaclav Kotesovec, Jan 11 2021

EXAMPLE

n = 10 has a(10) = 5 partitions into prime parts: 10 = 2 + 2 + 2 + 2 + 2 = 2 + 2 + 3 + 3 = 2 + 3 + 5 = 3 + 7 = 5 + 5.

n = 15 has a(15) = 12 partitions into prime parts: 15 = 2 + 2 + 2 + 2 + 2 + 2 + 3 = 2 + 2 + 2 + 3 + 3 + 3 = 2 + 2 + 2 + 2 + 2 + 5 = 2 + 2 + 2 + 2 + 7 = 2 + 2 + 3 + 3 + 5 = 2 + 3 + 5 + 5 = 2 + 3 + 3 + 7 = 2 + 2 + 11 = 2 + 13 = 3 + 3 + 3 + 3 + 3 = 3 + 5 + 7 = 5 + 5 + 5.

MAPLE

with(gfun):

t1:=mul(1/(1-q^ithprime(n)), n=1..51):

t2:=series(t1, q, 50):

t3:=seriestolist(t2); # fixed by Vaclav Kotesovec, Sep 14 2014

MATHEMATICA

CoefficientList[ Series[1/Product[1 - x^Prime[i], {i, 1, 50}], {x, 0, 50}], x]

f[n_] := Length@ IntegerPartitions[n, All, Prime@ Range@ PrimePi@ n]; Array[f, 57] (* Robert G. Wilson v, Jul 23 2010 *)

Table[Length[Select[IntegerPartitions[n], And@@PrimeQ/@#&]], {n, 0, 60}] (* Harvey P. Dale, Apr 22 2012 *)

a[n_] := a[n] = If[PrimeQ[n], 1, 0]; c[n_] := c[n] = Plus @@ Map[# a[#] &, Divisors[n]]; b[n_] := b[n] = (c[n] + Sum[c[k] b[n - k], {k, 1, n - 1}])/n; Table[b[n], {n, 1, 20}] (* Thomas Vogler, Dec 10 2015: Uses Euler transform, caches computed values, faster than IntegerPartitions[] function. *)

nmax = 100; pmax = PrimePi[nmax]; poly = ConstantArray[0, nmax + 1]; poly[[1]] = 1; poly[[2]] = 0; poly[[3]] = -1; Do[p = Prime[k]; Do[poly[[j + 1]] -= poly[[j + 1 - p]], {j, nmax, p, -1}]; , {k, 2, pmax}]; s = Sum[poly[[k + 1]]*x^k, {k, 0, Length[poly] - 1}]; CoefficientList[Series[1/s, {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 11 2021 *)

PROG

(PARI) N=66; x='x+O('x^N); Vec(1/prod(k=1, N, 1-x^prime(k))) \\ Joerg Arndt, Sep 04 2014

(Haskell)

a000607 = p a000040_list where

p _ 0 = 1

p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

-- Reinhard Zumkeller, Aug 05 2012

(Sage) [Partitions(n, parts_in=prime_range(n + 1)).cardinality() for n in range(100)] # Giuseppe Coppoletta, Jul 11 2016

(Python)

from sympy import primefactors

l = [1, 0]

for n in range(2, 101):

l.append(sum(sum(primefactors(k)) * l[n - k] for k in range(1, n + 1)) / n)

l # Indranil Ghosh, Jul 13 2017

(Magma) [1] cat [#RestrictedPartitions(n, {p:p in PrimesUpTo(n)}): n in [1..100]]; // Marius A. Burtea, Jan 02 2019

CROSSREFS

G.f. = 1 / g.f. for A046675. See A046113 for the ordered (compositions) version.

Cf. A046676, A048165, A004526, A051034, A000040, A001414, A000586 (distinct parts), A000041, A070214, A192541, A112021, A056768, A128515, A319265, A319266.

Row sums of array A116865 and of triangle A261013.

Column sums of A331416.

Partitions whose Heinz number is divisible by their sum of primes are A330953.

Partitions of whose sum of primes is divisible by their sum are A331379.

Cf. A000720, A014689, A331385, A331387, A331415, A331417.

Sequence in context: A029022 A140953 A112021 * A114372 A046676 A003114

Adjacent sequences: A000604 A000605 A000606 * A000608 A000609 A000610

KEYWORD

easy,nonn,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 2 18:07 EST 2022. Contains 358510 sequences. (Running on oeis4.)