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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000607 Number of partitions of n into prime parts.
(Formerly M0265 N0093)
53
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 for which A001414(k) = n. - Howard A. Landman, Sep 25 2001

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)

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.

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.

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

L. M. Chawla and S. A. Shad, 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, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

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

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

Vaclav Kotesovec, Wrong asymptotics of OEIS A000607? (MathOverflow)

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.

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(1-x^prime(k),k=1..infty).

See the partition arrays A116864 and A116865.

From Vaclav Kotesovec, Sep 15 2014: (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 proved by Vaughan in Ramanujan J. 15 (2008), p. 109-121: log(a(n)) = 2*Pi*sqrt(n/(3*log(n))) * (1 + log(log(n))/log(n) + O(1/log(n)))

(End)

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);

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] [From Robert G. Wilson v, Jul 23 2010]

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

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

CROSSREFS

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

Cf. A046676, A048165, A004526, A051034, A000040, A001414, A000586, A000041, A070214, A192541, A112021, A056768, A128515, A000586.

Row sums of array A116865.

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.

EXTENSIONS

Maple program fixed by Vaclav Kotesovec, Sep 14 2014

STATUS

approved

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.

Content is available under The OEIS End-User License Agreement .

Last modified October 1 00:26 EDT 2014. Contains 247498 sequences.