A184171 -id:A184171 - 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

A046675 Expansion of Product_{i>0} (1-x^{p_i}), where p_i are the primes.

Original entry on oeis.org

1, 0, -1, -1, 0, 0, 0, 0, 1, 1, 0, -1, 0, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, -1, 1, 1, 0, -1, 0, -1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1, 2, 0, 1, -1, 1, 0, 0, -3, 2, 1, 1, -2, 1, -2, 1, -2, 1, 0, 2, -3, 3, -1, 0, -2, 4, -1, 2, -4, 1, -1, 3, -5, 4, -1, 2, -3, 4, -4, 3, -5, 3, -1, 4, -8, 6, -1, 2, -7, 6, -4, 8, -6, 3

Offset: 0

N. J. A. Sloane

sign

The difference between the number of even partitions of n into distinct primes and the number of odd partitions of n into distinct primes. - T. D. Noe, Sep 08 2006

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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
H. Gupta, Partitions into distinct primes, Proc. Nat. Acad. Sci. India, 21 (1955), 185-187 [broken link].

Cf. A000607, A000586.

CoefficientList[Series[Product[1 - x^Prime[i], {i, 1, 100}], {x, 0, 100}], x] (* Vaclav Kotesovec, Sep 13 2018 *)
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) = A184171(n) - A184172(n). - R. J. Mathar, Jan 10 2011

Revised by N. J. A. Sloane, Jun 10 2012

A184198 Number of partitions of n into an even number of primes.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 2, 4, 4, 6, 5, 8, 7, 11, 10, 15, 13, 20, 17, 26, 23, 34, 29, 43, 38, 55, 49, 69, 62, 88, 78, 109, 97, 135, 122, 167, 150, 205, 186, 251, 227, 306, 277, 371, 337, 448, 407, 539, 492, 647, 591, 773, 707, 922, 845, 1096, 1005, 1298, 1193, 1535, 1412, 1809, 1667, 2127

Offset: 0

R. J. Mathar, Jan 10 2011

			n=18 can be partitioned in A000607(18)=19 ways into primes, of which a(18)=11 are even, namely 11+7, 13+5, 5+5+5+3, 7+5+3+3, 3+3+3+3+3+3, 7+7+2+2, 11+3+2+2, 5+3+3+3+2+2, 5+5+2+2+2+2, 7+3+2+2+2+2, 3+3+2+2+2+2+2+2.
The remaining A184199(18)=8 are odd.

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000

Cf. A000607, A048165, A184199, A184171.

Table[Count[IntegerPartitions[n],?(AllTrue[#,PrimeQ]&&EvenQ[Length[ #]]&)], {n,0,70}] (* The program uses the AllTrue function from Mathematica version 10 *) (* _Harvey P. Dale, Feb 16 2018 *)

parts(n, pred, y)={prod(k=1, n, if(pred(k), 1/(1-y*x^k) + O(x*x^n), 1))}
{my(n=80); Vec(parts(n, isprime, 1) + parts(n, isprime, -1))/2} \\ Andrew Howroyd, Dec 28 2017

a(n) = (A000607(n)+A048165(n))/2.

a(31)-a(69) corrected by Andrew Howroyd, Dec 28 2017

A184172 Number of partitions of n into an odd number of distinct primes.

Original entry on oeis.org

0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 3, 4, 3, 5, 3, 4, 4, 5, 5, 6, 6, 7, 5, 7, 7, 8, 8, 8, 9, 11, 9, 10, 11, 12, 12, 14, 13, 16, 14, 16, 15, 19, 17, 20, 20, 22, 20, 23, 24, 27, 26, 28, 27, 33, 30, 34, 34, 37, 36, 41, 40, 46, 43, 47, 46, 55, 50, 56

Offset: 0

Emeric Deutsch (suggested by R. J. Mathar), Jan 09 2011

nonn

			a(33) = 4 because we have [23,7,3], [19,11,3], [17,13,3], and [17,11,5].

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..2000 from Alois P. Heinz)

Cf. A000586, A184171, A184199.

g := 1/2*(Product(1+z^ithprime(k), k = 1 .. 120)-Product(1-z^ithprime(k), k = 1 .. 120)): gser := series(g, z = 0, 110): seq(coeff(gser, z, n), n = 0 .. 85);
# second Maple program
with(numtheory):
b:= proc(n, i) option remember;
      `if`(n=0, [1], `if`(i<1, [], zip((x, y)->x+y, b(n, i-1),
       [0, `if`(ithprime(i)>n, [], b(n-ithprime(i), i-1))[]], 0)))
    end:
a:= proc(n) local l; l:= b(n, pi(n));
      add(l[2*i], i=1..iquo(nops(l), 2))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Nov 15 2012

b[n_, i_] := b[n, i] = If[n == 0, {1}, If[i<1, {}, Plus @@ PadRight[{b[n, i-1], Join[{0}, If[Prime[i]>n, {}, b[n-Prime[i], i-1]]]}]]]; a[n_] := Module[{l}, l = b[n, PrimePi[n]]; Sum[l[[2*i]], {i, 1, Quotient[Length[l], 2]}]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 30 2014, after Alois P. Heinz *)

parts(n, pred, y)={prod(k=1, n, 1 + if(pred(k), y*x^k + O(x*x^n), 0))}
{my(n=80); (Vec(parts(n, isprime, 1)) - Vec(parts(n, isprime, -1)))/2} \\ Andrew Howroyd, Dec 28 2017

G.f.: (1/2)*[Product_{k>=1} (1+z^prime(k)) - Product_{k>=1} (1-z^prime(k))].
a(n) = Sum_{k>=0} A219180(n,2*k+1). - Alois P. Heinz, Nov 15 2012
a(n) + A184171(n) = A000586(n). - R. J. Mathar, Mar 31 2023

A339380 Number of partitions of n into an even number of primes (counting 1 as a prime).

Original entry on oeis.org

1, 0, 1, 1, 3, 2, 5, 4, 9, 7, 14, 11, 22, 18, 33, 27, 48, 40, 69, 58, 97, 82, 134, 114, 183, 157, 246, 212, 327, 284, 431, 376, 562, 493, 728, 640, 934, 825, 1191, 1056, 1508, 1341, 1899, 1694, 2377, 2126, 2960, 2654, 3668, 3297, 4523, 4075, 5554, 5015, 6792, 6145

Offset: 0

Ilya Gutkovskiy, Dec 02 2020

nonn

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

Index entries for sequences related to partitions

Cf. A000607, A008578, A027187, A034891, A184171, A184172, A184198, A184199, A338826, A339381, A339382, A339383.

b:= proc(n, i, t) option remember; (p->
      `if`(n=0, t, `if`(i<0, 0, b(n, i-1, t)+
      `if`(p>n, 0, b(n-p, i, 1-t)))))(`if`(i<1, 1, ithprime(i)))
    end:
a:= n-> b(n, numtheory[pi](n), 1):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 02 2020

nmax = 55; CoefficientList[Series[(1/2) ((1/(1 - x)) Product[1/(1 - x^Prime[k]), {k, 1, nmax}] + (1/(1 + x)) Product[1/(1 + x^Prime[k]), {k, 1, nmax}]), {x, 0, nmax}], x]
Table[Count[(Boole[PrimeQ/@(IntegerPartitions[n]/.(1->2))]),?(EvenQ[Length[#]] && FreeQ[ #,0]&)],{n,0,60}] (* _Harvey P. Dale, Aug 20 2024 *)

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

a(n) = (A034891(n) + A338826(n)) / 2.

A339381 Number of partitions of n into an odd number of primes (counting 1 as a prime).

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 3, 7, 5, 11, 9, 18, 14, 27, 22, 40, 33, 58, 48, 82, 69, 114, 97, 157, 134, 212, 183, 284, 246, 376, 327, 493, 431, 640, 562, 825, 728, 1056, 934, 1341, 1191, 1694, 1508, 2126, 1899, 2654, 2377, 3297, 2960, 4075, 3668, 5015, 4523, 6145, 5554, 7499

Offset: 0

Ilya Gutkovskiy, Dec 02 2020

nonn

			a(6) = 3 because we have [3, 2, 1], [2, 2, 2] and [2, 1, 1, 1, 1].

Index entries for sequences related to partitions

Cf. A000607, A008578, A027193, A034891, A184171, A184172, A184198, A184199, A338826, A339380, A339382, A339383.

b:= proc(n, i, t) option remember; (p->
      `if`(n=0, t, `if`(i<0, 0, b(n, i-1, t)+
      `if`(p>n, 0, b(n-p, i, 1-t)))))(`if`(i<1, 1, ithprime(i)))
    end:
a:= n-> b(n, numtheory[pi](n), 0):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 02 2020

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

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

a(n) = (A034891(n) - A338826(n)) / 2.

A339382 Number of partitions of n into an even number of distinct primes (counting 1 as a prime).

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 4, 4, 4, 4, 6, 5, 5, 5, 6, 6, 7, 7, 9, 8, 9, 8, 11, 10, 11, 12, 14, 12, 15, 14, 17, 16, 17, 17, 22, 20, 22, 21, 25, 24, 28, 27, 31, 30, 33, 31, 39, 36, 40, 40, 46, 42, 49, 47, 54, 53, 58, 55, 67, 63, 70, 68

Offset: 0

Ilya Gutkovskiy, Dec 02 2020

nonn

			a(16) = 3 because we have [13, 3], [11, 5] and [7, 5, 3, 1].

Index entries for sequences related to partitions

Cf. A000586, A008578, A036497, A067661, A184171, A184172, A184198, A184199, A298602, A339380, A339381, A339383.

s:= proc(n) option remember;
      `if`(n<1, n+1, ithprime(n)+s(n-1))
    end:
b:= proc(n, i, t) option remember; (p-> `if`(n=0, t,
      `if`(n>s(i), 0, b(n, i-1, t)+ `if`(p>n, 0,
       b(n-p, i-1, 1-t)))))(`if`(i<1, 1, ithprime(i)))
    end:
a:= n-> b(n, numtheory[pi](n), 1):
seq(a(n), n=0..100);  # Alois P. Heinz, Dec 02 2020

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

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

a(n) = (A036497(n) + A298602(n)) / 2.

A339383 Number of partitions of n into an odd number of distinct primes (counting 1 as a prime).

Original entry on oeis.org

0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 6, 6, 5, 7, 6, 8, 7, 8, 9, 10, 9, 12, 11, 12, 11, 14, 14, 16, 15, 17, 17, 20, 17, 21, 22, 24, 22, 27, 25, 30, 28, 31, 31, 36, 33, 40, 39, 42, 40, 47, 46, 53, 49, 55, 54, 63, 58, 68, 67, 73

Offset: 0

Ilya Gutkovskiy, Dec 02 2020

nonn

			a(21) = 4 because we have [17, 3, 1], [13, 7, 1], [13, 5, 3] and [11, 7, 3].

Index entries for sequences related to partitions

Cf. A000586, A008578, A036497, A067659, A184171, A184172, A184198, A184199, A298602, A339380, A339381, A339382.

s:= proc(n) option remember;
      `if`(n<1, n+1, ithprime(n)+s(n-1))
    end:
b:= proc(n, i, t) option remember; (p-> `if`(n=0, t,
      `if`(n>s(i), 0, b(n, i-1, t)+ `if`(p>n, 0,
       b(n-p, i-1, 1-t)))))(`if`(i<1, 1, ithprime(i)))
    end:
a:= n-> b(n, numtheory[pi](n), 0):
seq(a(n), n=0..100);  # Alois P. Heinz, Dec 02 2020

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

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

a(n) = (A036497(n) - A298602(n)) / 2.

A339432 Number of compositions (ordered partitions) of n into an even number of distinct primes.

Original entry on oeis.org

1, 0, 0, 0, 0, 2, 0, 2, 2, 2, 2, 0, 2, 2, 2, 2, 4, 24, 4, 2, 4, 26, 4, 48, 6, 50, 28, 48, 28, 72, 6, 74, 52, 98, 54, 96, 56, 120, 98, 122, 102, 864, 104, 146, 150, 866, 150, 1584, 154, 938, 200, 1632, 246, 3072, 226, 1706, 990, 3864, 1038, 4560, 348, 3914, 1828, 4634, 1162, 7488

Offset: 0

Ilya Gutkovskiy, Dec 04 2020

nonn

			a(16) = 4 because we have [13, 3], [3, 13], [11, 5] and [5, 11].

Alois P. Heinz, Table of n, a(n) for n = 0..5000
Index entries for sequences related to compositions

Cf. A000040, A184171, A219107, A332305, A339382, A339408, A339433.

b:= proc(n, i, p) option remember; `if`(n=0, irem(1+p, 2)*p!, (s->
     `if`(s>n, 0, b(n, i+1, p)+b(n-s, i+1, p+1)))(ithprime(i)))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..70);  # Alois P. Heinz, Dec 04 2020

b[n_, i_, p_] := b[n, i, p] = If[n == 0, Mod[1 + p, 2]*p!, Function[s, If[s > n, 0, b[n, i + 1, p] + b[n - s, i + 1, p + 1]]][Prime[i]]];
a[n_] := b[n, 1, 0];
Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Feb 26 2022, after Alois P. Heinz *)

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

A046675 Expansion of Product_{i>0} (1-x^{p_i}), where p_i are the primes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A184198 Number of partitions of n into an even number of primes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A184172 Number of partitions of n into an odd number of distinct primes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A339380 Number of partitions of n into an even number of primes (counting 1 as a prime).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339381 Number of partitions of n into an odd number of primes (counting 1 as a prime).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339382 Number of partitions of n into an even number of distinct primes (counting 1 as a prime).

Views

Author

Keywords

Examples