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