|
|
A000586
|
|
Number of partitions of n into distinct primes.
(Formerly M0022 N0004 N0039)
|
|
84
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
REFERENCES
|
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).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: Product_{k>=1} (1+x^prime(k)).
log(a(n)) ~ Pi*sqrt(2*n/(3*log(n))) [Roth and Szekeres, 1954]. - Vaclav Kotesovec, Sep 13 2018
|
|
EXAMPLE
|
n=16 has a(16) = 3 partitions into distinct prime parts: 16 = 2+3+11 = 3+13 = 5+11.
|
|
MAPLE
|
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)):
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Haskell)
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
(Python)
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))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|