# Computability of OEIS A034891 …partitions of n into prime parts (1 included)

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$:

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

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
cac[(n,k)]=a
return a,cac
def partf(n,k=1):
a,_=partf_(n,k,cac={})
return a

-
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