[Solved]: 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

Problem Detail: 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_2cdots 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_2cdots 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, dneq 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.

Asked By : justice league

Answered By : Yuval Filmus

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_1ldots p_t)$ is given by A000670, and $g(p_1^2 p_2ldots p_t)$ is given by A005649 or A172109.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13336 Ask a Question Download Related Notes/Documents