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

Question

My problem. Given $n$, I want to count the number of valid multisets $S$. A multiset $S$ is valid if

• The sum of the elements of $S$ is $n$, and
• Every number from $1$ to $n$ can be expressed uniquely as a sum of some of the elements of $S$.

Example. For example if $n=5$ then $\{1,1,1,1,1\}, \{1,2,2\}, \{1,1,3\}$ are valid.

However, $S=\{1,1,1,2\}$ is invalid because 2 can be formed by both $\{1,1\}$ and $\{2\}$ (i.e., 2 can be expressed as both $2=1+1$ and $2=2$), so the second condition doesn't hold. Similarly 3 can be formed by $\{2,1\}$ and $\{1,1,1\}$.

$S=\{1,2,4$} is also invalid because all numbers from $1$ to $5$ can be uniquely made, but the sum of the elements of $S$ is not $5$.

---

I've tried to find a good algorithm for this problem for quite some time but cannot solve it. It is from codechef. I've seen some of the submitted solutions but I still couldn't get the logic for solving the problem. NOTE: The time limit for the question is 10 seconds and $n<10^9$

For a multiset I will use the notation $S = \{(a_1, c_1), (a_2, c_2) ... \}$ $a_i<a_j$ if $i<j$, which means $a_i$ occurs $c_i$ times in multiset S.

Till now I have drawn some conclusions

• First element of the required sorted multiset should be $1$
• Let $S=\{1,a_2 \cdots a_k\} | a_1 \leq a_2\cdots \leq a_k $ be a set following the two properties then $\forall r<k \ \ a_{r+1} = a_r \text{ or } (\sum_{i=0}^ra_i) + 1$
• Let $S=\{(1,c_1),(a_2,c_2) \cdots (a_k,c_k)\} | a_1 \leq a_2\cdots \leq a_k$, where $a_i$ is occurring $c_i$ times, follows the required properties then from the above conclusion we can say that $\forall i \ a_i|n+1$ and $a_i | a_j$ if $j > i$ .
  Proof: $a_{i+1} = (a_ic_i + a_i -1 ) + 1 \Rightarrow a_i | a_{i+1}$
• Now consider $S=\{ \underbrace{1,1 \cdots 1}_{d-1},d,d \cdots d,dm_1, dm_1 \cdots dm_1,dm_2, dm_2 \cdots dm_2, \cdots \}$ i.e. all the subsequent numbers after 1 will be a multiple of $d$. So let $f(n)$ be the count of such multiset possible then $f(n) = \sum_{d|n+1, d\neq 1} f(\frac{n-(d-1)}{d})$ where I am summing over all possible number of $1's$($=d-1$). In other terms $f(n-1)=g(n)=\sum_{d|n,d \neq n}g(d)$

Finally my problem is reduced to this - find $g(n)$ in an efficient way so that it doesnt exceed the time limit.

Answer 1

Here is what the fastest solution is doing. It is indeed computing your function $$ g(n) = \sum_{\substack{d \mid n \\ d < 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.

Answer 2

OK, so you have a recurrence relation for $g(\cdot)$ (see the end of your question).

At this point it seems like a natural approach would be to write down the recursive algorithm to compute $g(n)$, and apply memoization so you don't compute $g(i)$ more than once. In other words, when you compute $g(i)$, you store it in a hash table that maps $i \mapsto g(i)$; if you need to know $g(i)$ again in the future, you can look it up in the hash table.

This does require factoring $n$, but there are efficient algorithms for factoring $n$ when $n\le 10^9$.

You might also look up the sequence $g(1),g(2),g(3),g(4),g(5),\ldots$ in the On-Line Encyclopedia of Integer Sequences. If you find the sequence in their encyclopedia, sometimes they will provide additional helpful information (e.g., efficient algorithms for computing the sequence). That admittedly might take the fun out of things, though.

Answer 3

Here's a hint to get you started. Apply standard dynamic programming algorithms for enumerating the set of partitions of an integer, and add some logic to check which of those allows for unique change-making by iteratively checking all sums, making change, and verifying uniqueness.

In a bit more detail: Suppose you have a multiset $S$. Given a number $i$ with $1 \le i \le n$, how could you identify a submultiset of $S$ that sums to $i$? How could you check whether that submultiset is unique? Try to adapt standard dynamic programming techniques for making change. (See also this question.)

Given a multiset $S$, how could you check whether it satisfies the second condition, i.e., whether every number from 1 to $n$ can be uniquely expressed as a sum of a submultiset of $S$ (the unique change-making condition)? This should be pretty easy, if you solved the previous one.

let $P(n)$ denote the list of multisets that satisfy both of your conditions. If you knew $P(1), P(2), \dots, P(n)$, how could you use that information to construct $P(n+1)$? Here you might want to adapt standard dynamic programming techniques for enumerating the partitions of an integer.

---

Here's an approach that will probably be better.

Suppose $S$ is a multiset that satisfies both of your conditions (for $n$). How can we extend it to get a multiset $T$ that has one element more? In other words, how can we identify all the ways to add one more element to $S$, to get a new multiset $T$ that satisfies both of your conditions (for some $n'$)?

Answer: if $x$ can be expressed as a sum of some of the elements of $S$, then there's no point in adding it to $S$: that would cause $T$ to violate the uniqueness condition. So, we can enumerate all integers $x$ that cannot be expressed as a sum of some of the elements of $S$; each one is something that could potentially be added to $S$ to get a new multiset $T$ that will satisfy both conditions (for some other $n$).

Moreover, it is possible to enumerate which integers can be expressed as a sum of some of the elements of $S$, and which cannot, using dynamic programming. You build a two-dimensional array $A[1\ldots |S|,1 \ldots n]$ of booleans, where $A[i,j]$ is true if there is a way to express the integer $j$ as a sum of some of the first $i$ elements of $S$ (only the first $i$ elements of $S$ are eligible to be used; where $S$ has been sorted, so $S=\{s_1,s_2,\dots,s_k\}$ and $s_1\le s_2 \le \cdots \le s_k$). Note that $A[i,j]$ can be computing using the values of $A[1\ldots i-1, 1\ldots j-1]$: in particular, $A[i,j] = A[i-1,j] \lor A[i-1,j-s_i]$ if $j>s_i$, or $A[i,j]=A[i-1,j]$ otherwise. This enables us to identify all numbers that are candidates to be added to $S$.

Next, for each candidate extension $T$ of $S$ (obtained by adding one element to $S$), we want to check whether $T$ satisfies both conditions. Let $n$ denote the sum of elements of $S$, and $n'$ the sum of elements of $T$. We need to check whether every integer in the range $n+1,n+2,\ldots,n'$ can be expressed as a sum of some of the elements of $T$. This too can be solved using dynamic programming, using standard algorithms for change-making. (In fact, if you still have the array $A$ mentioned above you can easily extend it a little bit to solve this problem: we make it an array $A[1\ldots |T|, 1 \ldots n']$, continue to fill in all of the additional entries, and make sure that $A[|T|,n+1], A[|T|,n+2], \ldots, A[|T|,n']$ are all true.) So, now we can enumerate all multisets $T$ that extend $S$ by a single element and that satisfy both conditions.

This immediately suggests an algorithm to enumerate all multisets $S$ that satisfy your condition, for all $n$ up to some bound, say $n\le 20$. We'll have an array $P[1\ldots 20]$, where $P[5]$ stores all multisets $S$ that sum to 5, and generally, $P[n]$ stores the set of all multisets $S$ that sum to $n$.

Next, we can fill in $P[n]$ iteratively. Start by setting $P[1]$ to contain just the one multiset $\{1\}$. Next, for each $n$ (counting up from 1 to 20), for each $S \in P[n]$, enumerate all possible extensions $T$ of $S$ (using the techniques above), let $n'$ denote the sum of the elements of $T$, and insert $T$ into $P[n']$ if it isn't already present and if $n' \le 20$.

This should be pretty doable. Good luck! Have fun! Working through the details will be a good learning-exercise in dynamic programming.