A070215 -id:A070215 - cp's OEIS frontend

A000586 Number of partitions of n into distinct primes.

1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 5, 5, 6, 5, 6, 7, 6, 9, 7, 9, 9, 9, 11, 11, 11, 13, 12, 14, 15, 15, 17, 16, 18, 19, 20, 21, 23, 22, 25, 26, 27, 30, 29, 32, 32, 35, 37, 39, 40, 42, 44, 45, 50, 50, 53, 55, 57, 61, 64, 67, 70, 71, 76, 78, 83, 87, 89, 93, 96

Offset: 0

N. J. A. Sloane

			n=16 has a(16) = 3 partitions into distinct prime parts: 16 = 2+3+11 = 3+13 = 5+11.

H. Gupta, Certain averages connected with partitions. Res. Bull. Panjab Univ. no. 124 1957 427-430.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in two entries, N0004 and N0039).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Edray Herber Goins and Talitha M. Washington, On the generalized climbing stairs problem, Ars Combin. 117 (2014), 183-190. MR3243840 (Reviewed), arXiv:0909.5459 [math.CO], 2009.
H. Gupta, Partitions into distinct primes, Proc. Nat. Acad. Sci. India, 21 (1955), 185-187. [broken link]
BongJu Kim, Partition number identities which are true for all set of parts, arXiv:1803.08095 [math.CO], 2018.
Vaclav Kotesovec, Plot of log(a(n)) / log(Qas(n)) for n = 2..10^8, for Qas see the formula (25) from the article by Murthy, Brack and Bhaduri, p. 7.
M. V. N. Murthy, M. Brack, R. K. Bhaduri, On the asymptotic distinct prime partitions of integers, arXiv:1904.02776 [math.NT], Mar 22 2019.
K. F. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions, Quart. J. Math., Oxford Ser. (2) 5 (1954), 241-259.

Cf. A000041, A070215, A000607 (parts may repeat), A112022, A000009, A046675, A319264, A319267.

a000586 = p a000040_list where
   p _  0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Aug 05 2012

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+`if`(ithprime(i)>n, 0, b(n-ithprime(i), i-1))))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Nov 15 2012

CoefficientList[Series[Product[(1+x^Prime[k]), {k, 24}], {x, 0, Prime[24]}], x]
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i-1] + If[Prime[i] > n, 0, b[n - Prime[i], i-1]]]]; a[n_] := b[n, PrimePi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)
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]] += poly[[j - p]], {j, nmax + 1, p + 1, -1}];, {k, 2, pmax}]; poly (* Vaclav Kotesovec, Sep 20 2018 *)

a(n,k=n)=if(n<1, !n, my(s);forprime(p=2,k,s+=a(n-p,p-1));s) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import isprime, primerange
from functools import cache
@cache
def a(n, k=None):
    if k == None: k = n
    if n < 1: return int(n == 0)
    return sum(a(n-p, p-1) for p in primerange(1, k+1))
print([a(n) for n in range(83)]) # Michael S. Branicky, Sep 03 2021 after Charles R Greathouse IV

G.f.: Product_{k>=1} (1+x^prime(k)).
a(n) = A184171(n) + A184172(n). - R. J. Mathar, Jan 10 2011
a(n) = Sum_{k=0..A024936(n)} A219180(n,k). - Alois P. Heinz, Nov 13 2012
log(a(n)) ~ Pi*sqrt(2*n/(3*log(n))) [Roth and Szekeres, 1954]. - Vaclav Kotesovec, Sep 13 2018

Entry revised by N. J. A. Sloane, Jun 10 2012

A056768 Number of partitions of the n-th prime into parts that are all primes.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 17, 23, 40, 87, 111, 219, 336, 413, 614, 1083, 1850, 2198, 3630, 5007, 5861, 9282, 12488, 19232, 33439, 43709, 49871, 64671, 73506, 94625, 221265, 279516, 394170, 441250, 766262, 853692, 1175344, 1608014, 1975108, 2675925

Offset: 1

Brian Galebach, Aug 16 2000

nonn

			a(4) = 3 because the 4th prime is 7 which can be partitioned using primes in 3 ways: 7, 5 + 2, and 3 + 2 + 2.
In connection with the 6th prime 13, for instance, we have the a(6) = 9 prime partitions: 13 = 2 + 2 + 2 + 2 + 2 + 3 = 2 + 2 + 2 + 2 + 5 = 2 + 2 + 2 + 7 = 2 + 2 + 3 + 3 + 3 = 2 + 3 + 3 + 5 = 2 + 11 = 3 + 3 + 7 = 3 + 5 + 5.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 4000 terms from Alois P. Heinz)

Cf. A000041, A000607, A100118, A276687, A070215 (distinct parts).

a056768 = a000607 . a000040  -- Reinhard Zumkeller, Aug 05 2012

b:= proc(n, i) option remember; `if`(n=0 or i=2
       and n::even, 1, `if`(i=2 or n=1, 0,
       b(n, prevprime(i)))+`if`(i>n, 0, b(n-i, i)))
    end:
a:= n-> b(ithprime(n)$2):
seq(a(n), n=1..50);  # Alois P. Heinz, Sep 15 2016

Table[Count[IntegerPartitions[n],?(AllTrue[#,PrimeQ]&)],{n,Prime[ Range[ 40]]}] (* The program uses the AllTrue function from Mathematica version 10 *) (* _Harvey P. Dale, Mar 07 2015 *)
n=40;ser=Product[1/(1-x^Prime[i]),{i,1,n}];Table[SeriesCoefficient[ser,{x,0,Prime[i]}],{i,1,n}] (* Gus Wiseman, Sep 14 2016 *)

a(n) = A000607(prime(n)).
a(n) = A168470(n) + 1. - Alonso del Arte, Feb 15 2014, restating the corresponding formula given by R. J. Mathar for A168470.
a(n) = [x^prime(n)] Product_{k>=1} 1/(1 - x^prime(k)). - Ilya Gutkovskiy, Jun 05 2017

More terms from James Sellers, Aug 25 2000

A307610 Number of partitions of prime(n) into consecutive primes.

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 1, 2, 2, 1, 1, 3, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 3, 1, 1, 2, 1, 1, 3, 1, 2, 2, 2, 1, 3, 1, 1, 1, 5, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 3, 2, 2, 2, 1, 2, 1, 2, 2, 3, 2, 2, 1, 1, 2

Offset: 1

Ilya Gutkovskiy, Apr 18 2019

nonn

a(n) - 1 = number of partitions of prime(n) into two or more consecutive primes. - Ray Chandler, Sep 26 2023

			prime(13) = 41 = 2 + 3 + 5 + 7 + 11 + 13 = 11 + 13 + 17, so a(13) = 3.

Ray Chandler, Table of n, a(n) for n = 1..1000

Cf. A000040, A034707, A054845, A056768, A070215, A084143.

a(n) = [x^prime(n)] Sum_{i>=1} Sum_{j>=i} Product_{k=i..j} x^prime(k).

a(n) = A054845(A000040(n)).

A316154 Number of integer partitions of prime(n) into a prime number of prime parts.

Original entry on oeis.org

0, 0, 1, 2, 3, 5, 9, 12, 19, 39, 50, 93, 136, 166, 239, 409, 682, 814, 1314, 1774, 2081, 3231, 4272, 6475, 11077, 14270, 16265, 20810, 23621, 30031, 68251, 85326, 118917, 132815, 226097, 251301, 342448, 463940, 565844, 759873, 1015302, 1117708, 1787452, 1961624

Offset: 1

Gus Wiseman, Jun 25 2018

nonn

			The a(7) = 9 partitions of 17 into a prime number of prime parts: (13,2,2), (11,3,3), (7,7,3), (7,5,5), (7,3,3,2,2), (5,5,3,2,2), (5,3,3,3,3), (5,2,2,2,2,2,2), (3,3,3,2,2,2,2).

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from Andrew Howroyd)

Cf. A000040, A000586, A000607, A038499, A056768, A064688, A070215, A085755, A302590, A316092, A316153, A316185, A344782.

b:= proc(n, p, c) option remember; `if`(n=0 or p=2,
      `if`(n::even and isprime(c+n/2), 1, 0),
      `if`(p>n, 0, b(n-p, p, c+1))+b(n, prevprime(p), c))
    end:
a:= n-> b(ithprime(n)$2, 0):
seq(a(n), n=1..50);  # Alois P. Heinz, Jun 26 2018

Table[Length[Select[IntegerPartitions[Prime[n]],And[PrimeQ[Length[#]],And@@PrimeQ/@#]&]],{n,20}]
(* Second program: *)
b[n_, p_, c_] := b[n, p, c] = If[n == 0 || p == 2, If[EvenQ[n] && PrimeQ[c + n/2], 1, 0], If[p>n, 0, b[n - p, p, c + 1]] + b[n, NextPrime[p, -1], c]];
a[n_] := b[Prime[n], Prime[n], 0];
Array[a, 50] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

seq(n)={my(p=vector(n,k,prime(k))); my(v=Vec(1/prod(k=1, n, 1 - x^p[k]*y + O(x*x^p[n])))); vector(n, k, sum(i=1, k, polcoeff(v[1+p[k]], p[i])))} \\ Andrew Howroyd, Jun 26 2018

a(n) = A085755(A000040(n)). - Alois P. Heinz, Jun 26 2018

Terms a(21) and beyond from Andrew Howroyd, Jun 26 2018

A316185 Number of strict integer partitions of the n-th prime into a prime number of prime parts.

Original entry on oeis.org

0, 0, 1, 1, 0, 1, 0, 2, 2, 3, 5, 5, 6, 8, 10, 13, 18, 20, 26, 32, 34, 45, 54, 66, 90, 106, 117, 135, 142, 165, 269, 311, 375, 398, 546, 579, 689, 823, 938, 1107, 1301, 1352, 1790, 1850, 2078, 2153, 2878, 3811, 4241, 4338, 4828, 5495, 5637, 7076, 8000, 9032

Offset: 1

Gus Wiseman, Jun 25 2018

nonn

			The a(14) = 8 partitions of 43 into a prime number of distinct prime parts: (41,2), (31,7,5), (29,11,3), (23,17,3), (23,13,7), (19,17,7), (19,13,11), (17,11,7,5,3).

Alois P. Heinz, Table of n, a(n) for n = 1..2000

Cf. A000586, A000607, A038499, A045450, A056768, A064688, A070215, A085755, A302590, A316092, A316153, A316154.

h:= proc(n) option remember; `if`(n=0, 0,
     `if`(isprime(n), n, h(n-1)))
    end:
b:= proc(n, i, c) option remember; `if`(n=0,
      `if`(isprime(c), 1, 0), `if`(i<2, 0, b(n, h(i-1), c)+
      `if`(i>n, 0, b(n-i, h(min(n-i, i-1)), c+1))))
    end:
a:= n-> b(ithprime(n)$2, 0):
seq(a(n), n=1..56);  # Alois P. Heinz, May 26 2021

Table[Length[Select[IntegerPartitions[Prime[n]],And[UnsameQ@@#,PrimeQ[Length[#]],And@@PrimeQ/@#]&]],{n,10}]
(* Second program: *)
h[n_] := h[n] = If[n == 0, 0, If[PrimeQ[n], n, h[n - 1]]];
b[n_, i_, c_] := b[n, i, c] = If[n == 0,
     If[PrimeQ[c], 1, 0], If[i < 2, 0, b[n, h[i - 1], c] +
     If[i > n, 0, b[n - i, h[Min[n - i, i - 1]], c + 1]]]];
a[n_] := b[Prime[n], Prime[n], 0];
Array[a, 56] (* Jean-François Alcover, Jun 11 2021, after Alois P. Heinz *)

seq(n)={my(p=vector(n, k, prime(k))); my(v=Vec(prod(k=1, n, 1 + x^p[k]*y + O(x*x^p[n])))); vector(n, k, sum(i=1, k, polcoeff(v[1+p[k]], p[i])))} \\ Andrew Howroyd, Jun 26 2018

a(n) = A045450(A000040(n)).

More terms from Alois P. Heinz, Jun 26 2018

A280245 Expansion of Product_{k>=1} (1 + x^prime(k))^2.

Original entry on oeis.org

1, 0, 2, 2, 1, 6, 1, 8, 6, 6, 14, 6, 18, 14, 18, 24, 23, 30, 35, 38, 46, 54, 55, 74, 72, 90, 100, 106, 128, 136, 152, 178, 185, 216, 238, 252, 302, 308, 359, 390, 420, 478, 512, 564, 628, 668, 745, 810, 871, 974, 1035, 1140, 1238, 1336, 1459, 1586, 1700, 1868, 1993, 2168, 2354, 2512, 2751, 2930, 3177, 3418, 3677, 3960

Offset: 0

Ilya Gutkovskiy, Dec 29 2016

nonn

Number of partitions of n into distinct prime parts, with 2 types of each part.

Self-convolution of A000586. - Ilya Gutkovskiy, Jan 19 2018

			a(5) = 6 because we have [5], [5'], [3, 2], [3', 2], [3, 2'], [3', 2'].

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from Seiichi Manyama)
Eric Weisstein's World of Mathematics, Prime Partition
Index entries for related partition-counting sequences

Cf. A000009, A000586, A000607, A022567, A070215.

nmax = 67; CoefficientList[Series[Product[(1 + x^Prime[k])^2, {k, 1, nmax}], {x, 0, nmax}], x]

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

log(a(n)) ~ 2*Pi*sqrt(n/(3*log(n/2))). - Vaclav Kotesovec, Jan 12 2021

A299168 Number of ordered ways of writing n-th prime number as a sum of n primes.

Original entry on oeis.org

1, 0, 0, 0, 5, 6, 42, 64, 387, 5480, 10461, 113256, 507390, 1071084, 4882635, 44984560, 382362589, 891350154, 7469477771, 33066211100, 78673599501, 649785780710, 2884039365010, 22986956007816, 306912836483025, 1361558306986280, 3519406658042964

Offset: 1

Ilya Gutkovskiy, Feb 04 2018

nonn

			a(5) = 5 because fifth prime number is 11 and we have [3, 2, 2, 2, 2], [2, 3, 2, 2, 2], [2, 2, 3, 2, 2], [2, 2, 2, 3, 2] and [2, 2, 2, 2, 3].

Alois P. Heinz, Table of n, a(n) for n = 1..400

Cf. A000040, A000586, A000607, A023360, A056768, A070215, A073610, A098238, A117278, A121303, A219180, A224344, A259254, A265112, A341459.

b:= proc(n, t) option remember;
      `if`(n=0, `if`(t=0, 1, 0), `if`(t<1, 0, add(
      `if`(isprime(j), b(n-j, t-1), 0), j=1..n)))
    end:
a:= n-> b(ithprime(n), n):
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 13 2021

Table[SeriesCoefficient[Sum[x^Prime[k], {k, 1, n}]^n, {x, 0, Prime[n]}], {n, 1, 27}]

a(n) = [x^prime(n)] (Sum_{k>=1} x^prime(k))^n.

A071837 Numbers k with the property that in the prime factorization of k all prime exponents are prime, their sum is also prime and equals the sum of distinct prime factors of k.

Original entry on oeis.org

4, 27, 72, 108, 800, 3125, 12500, 247808, 823543, 22579200, 37879808, 190512000, 266716800, 428652000, 529200000, 600112800, 868020300, 1190700000, 1234800000, 1452124800, 2420208000, 2679075000, 3267280800, 3307500000, 4984012800, 6994132992, 7351381800, 7441875000, 7717500000, 9376762500

Offset: 1

Reinhard Zumkeller, Jun 08 2002

			800 is a term as 800 = 2^5 * 5^2, 2+5 = 5+2 = 7, and 7,5,2 are primes.

Cf. A054411, A008472, A001222, A056166, A070215.

A240983 and A051674 are subsequences. - Zak Seidov, Aug 21 2014

terms = 24; fromFactors[s_List] := (Times @@ (s^#)&) /@ Permutations[s]; Clear[f]; f[n_] := f[n] = (ssp = Select[Subsets[Prime[Range[n]]] // Rest, PrimeQ[Total[#]]&]; fromFactors /@ ssp // Flatten // Union // PadRight[#, terms]& ); f[2]; f[n = 4]; While[Print["n = ", n]; f[n] != f[n-2], n = n+2]; f[n] (* Jean-François Alcover, Jul 20 2015 *)

isok(n) = {f = factor(n); for (i=1, #f~, if (! isprime(f[i, 2]), return (0));); isprime(se = sum(i=1, #f~, f[i, 2])) && (se == sum(i=1, #f~, f[i, 1]));} \\ Michel Marcus, Aug 21 2014

from sympy import factorint, isprime
A071837 = []
for n in range(1,10**5):
    f = factorint(n)
    fp, fe = list(f.keys()),list(f.values())
    if sum(fp) == sum(fe) and isprime(sum(fe)) and all([isprime(e) for e in fe]):
        A071837.append(n)
# Chai Wah Wu, Aug 27 2014

Missing terms inserted by Sean A. Irvine, Aug 17 2024

A229219 a(n) = maximal length of partitions of prime(n) into distinct primes.

Original entry on oeis.org

1, 1, 2, 2, 1, 2, 4, 3, 4, 4, 4, 4, 6, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 14, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14

Offset: 1

Arkadiusz Wesolowski, Nov 10 2013

			a(11) = 4 because prime(11) = 31 = 2 + 3 + 7 + 19, but 31 is not a sum of 5 or more distinct primes.

David A. Corneth, Table of n, a(n) for n = 1..10000
G. L. Honaker, Jr. and Chris Caldwell, Prime Curios! 11
Wikipedia, Knapsack problem

Cf. A000040, A070215.

nn = 20; p = Prime[Range[nn]]; s = Subsets[p]; t2 = Table[Select[s, Total[#] == n &], {n, p}]; Table[Max[Length /@ t2[[n]]], {n, nn}] (* T. D. Noe, Nov 13 2013 *)

A316153 Heinz numbers of integer partitions of prime numbers into a prime number of prime parts.

Original entry on oeis.org

15, 33, 45, 93, 153, 177, 275, 327, 369, 405, 425, 537, 603, 605, 775, 831, 891, 1025, 1059, 1125, 1413, 1445, 1475, 1641, 1705, 1719, 1761, 2057, 2075, 2319, 2511, 2577, 2979, 3175, 3179, 3189, 3459, 3485, 3603, 3609, 3825, 3925, 4299, 4475, 4497, 4565, 4581

Offset: 1

Gus Wiseman, Jun 25 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of integer partitions of prime numbers into a prime number of prime parts, preceded by their Heinz numbers, begins:
   15: (3,2)
   33: (5,2)
   45: (3,2,2)
   93: (11,2)
  153: (7,2,2)
  177: (17,2)
  275: (5,3,3)
  327: (29,2)
  369: (13,2,2)
  405: (3,2,2,2,2)
  425: (7,3,3)
  537: (41,2)
  603: (19,2,2)
  605: (5,5,3)
  775: (11,3,3)
  831: (59,2)
  891: (5,2,2,2,2)

Cf. A000586, A000607, A038499, A056239, A056768, A064688, A070215, A085755, A302590, A316092, A316151.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],And[PrimeQ[PrimeOmega[#]],PrimeQ[Total[primeMS[#]]],And@@PrimeQ/@primeMS[#]]&]

cp's OEIS Frontend

A000586 Number of partitions of n into distinct primes.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A056768 Number of partitions of the n-th prime into parts that are all primes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A307610 Number of partitions of prime(n) into consecutive primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A316154 Number of integer partitions of prime(n) into a prime number of prime parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A316185 Number of strict integer partitions of the n-th prime into a prime number of prime parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A280245 Expansion of Product_{k>=1} (1 + x^prime(k))^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A299168 Number of ordered ways of writing n-th prime number as a sum of n primes.

Views

Author

Keywords