Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

On the seqfan mailing list RGWv gave short algorithm for computing A000041 number of partitions of n the partition numbers:

f[1, 1] = 1; f[n_, k_] := f[n, k] = If[n < 0, 0, If[k > n, 0, If[k == n, 1, f[n, k + 1] + f[n - k, k]]]]

So number of partitions of $n$ is $f(n,1)$ where $f(n,k)$ is the recurrence:

$$f(1,1)=1$$ $$f(n,k)=1, k=n$$ $$f(n,k)=0 \text{ if } k>n \text{ or } n<0$$ $$f(n,k)=f(n,{k+1}) + f(n-k,k)$$

Blindly changing $k+1$ to next_prime(k) (see sage implementation) appears to give A034891 Number of different products of partitions of n; partitions of n into prime parts (1 included); number of distinct orders of Abelian subgroups of symmetric group S_n.

This was verfied for the first 1000 terms, the last term being > $10^{19}$.

Number of partitions of $n$ into prime parts (1 included) seems $f(n,1)$ where $f(n,k)$ is the recurrence:

$$f(1,1)=1$$ $$f(n,k)=1, k=n$$ $$f(n,k)=0 \text{ if } k>n \text{ or } n<0$$ $$f(n,k)=f(n,nextprime(k)) + f(n-k,k)$$

Is this a correct way to compute A034891?

$k+1$ in the original formula seems a successor relation.

Other changes of $k+1$:

$2k$ seems A018819 Binary partition function: number of partitions of n into powers of 2

$3k$ seems A062051 Number of partitions of n into parts which are powers of 3

|next_non_prime(k)| A002095 Number of partitions of n into nonprime parts.

|next_fibonacci(k)| A003107 Number of partitions of n into Fibonacci parts with a single type of 1

Update: According to this code Number of partitions of n into nonzero triangular numbers number of partitions of $n$ into increasing sequence $g(k)$ seems $f(n,1)$ where $f(n,k)$ is the recurrence:

$$f(n,k)=f(n-g(k),k) + f(n,k+1), \ \ n>g(k)$$ $$f(n,k)=1, \ n=g(k)$$ $$f(n,k)=0 \text{ otherwise }$$

#sage implementation for A034891
#usage: [partf(i) for i in xrange(1,100)]
def partf_(n,k,cac={}):
    if n==1 and k==1:
        return 1,cac
    if nn:  return 0,cac
    if k==n:  return 1,cac
    if (n,k) in cac:  return cac[(n,k)],cac
    #next_prime(k) can be changed to 2*k,3*k,next_non_prime(k),next_fibonacci(k)
    a,cac=partf_(n,next_prime(k),cac) #partf_(n,k+1,cac)
    b,cac = partf_(n-k,k,cac) # partf_(n-k,k,cac)
    a += b
    return a,cac
def partf(n,k=1):
    return a
share|improve this question
The algorithm you have given is based on f[n, k] being the number of partitions of n into parts of size at least k. It uses k+1 to iterate, because it wants parts which include all natural numbers. Using a different successor function, the "partial function" f[n,k] might measure the number of partitions of n into primes no smaller than k - you just have to think through the interpretation a little. The treatment of 1 as a part is significant too. f[1, 1] = 1 implies 1 is a part. If not, more care is needed over defining a base case. –  Mark Bennet Jan 25 '11 at 9:39
And care over the case of equality too. –  Mark Bennet Jan 25 '11 at 9:41
@Mark without caring about the equality the first 1000 terms coincide. –  joro Jan 25 '11 at 9:57
@joro I think you just have to work through some small cases to see what the equality case is doing here - which partition is it picking up that isn't included in the other case? It can't be the partition into 1 part (as in the general partitions case) because n is not always prime. –  Mark Bennet Jan 25 '11 at 11:36
k runs in 1 union the primes and the equality adds 1. n changes as n-k. does this mean this is just hidden enumeration of all partitions? (i am somewhat puzzled because on the seqfan list was claimed that the number of partitions of 10^9 was computed in 40 seconds probably using memoization and this would seem to require a lot of RAM IMO). –  joro Jan 25 '11 at 11:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.