Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset
Here is what the fastest solution is doing. It is indeed computing your function
$$ g(n) = \sum_{\substack{d \mid n \\ d &lt; n}} g(d), \quad g(1) = 1. $$
Given $n$, we factor it (see below) and then compute all factors (see below) $f_1,\ldots,f_m$ in some order such that $f_i|f_j$ implies $i \leq j$ (property P). We now compute $g$ according to the formula by going over the factors in the given order. Property P ensures that when we compute $g(d)$, we have already computed $g(e)$ for all non-trivial factors $e$ of $d$. There is also an optimization (see below).

In more detail, we go over the factors in order, and for each factor $f_i$, we find all of its non-trivial factors by checking which of $f_1,\ldots,f_{i-1}$ divides $f_i$.

Factoring: Preprocessing: we make a list of all primes below $10^9$ using the Eratosthenes sieve. Given $n$, we simply use trial division.

Generating all factors: This is done recursively. Suppose $n = p_1^{k_1} \cdots p_t^{k_t}$. We run $t$ nested loops $l_1 \in \{0,\ldots,k_1\},\ldots,l_t \in \{0,\ldots,k_t\}$, and output $p_1^{l_1}\cdots p_t^{l_t}$. You can prove property P by induction.

Optimization: Since the program is run on several inputs, we can use memoization to save time across different inputs. We only memoize small values (up to $10^5$), and this allows us to store all memoized values in an array. The array is initialized with zeroes, and so we can tell which values are already known (since all computed values are positive).



If the prime factorization of $n+1$ is $p_1^{k_1},\ldots,p_t^{k_t}$, then $f(n)$ depends only on $(k_1,\ldots,k_t)$, and in fact only on the sorted version of this vector. Every number below $10^9$ has at most $29$ prime factors (with repetition), and since $p(29)=4565$, it seems feasible to compute $f$ (or rather $g$) for all of them, recursively. This solution could be faster if there were many different inputs; as it is, there are at most $10$.

It is also possible that this function, mapping partitions to the corresponding $g$, has an explicit analytic form. For example, $g(p^k) = 2^{k-1}$, $g(p_1\ldots p_t)$ is given by A000670, and $g(p_1^2 p_2\ldots p_t)$ is given by A005649 or A172109.