I want to know in how many ways can we represent a number $x$ as a sum of numbers from a given set of numbers $\{a_1.a_2,a_3,...\}$. Each number can be taken more than once.

For example, if $x=4$ and $a_1=1, a_2=2$, then the ways of representing $x=4$ are:

  • $1+1+1+1$
  • $1+1+2$
  • $1+2+1$
  • $2+1+1$
  • $2+2$

Thus the number of ways $=5$.

I want to know if there exists a formula or some other fast method to do so. I can't brute force through it. I want to write code for it.

Note: $x$ can be as large as $10^{18}$. The number of terms $a_1,a_2,a_3,\dots$ can be up to $15$, and each of $a_1,a_2,a_3,\dots$ can also be only up to $15$.

  • 1
    $\begingroup$ It looks to me that you want to count the number of restricted compositions, based on the fact that you consider $1+1+2$ and $1+2+1$ to be distinct. $\endgroup$ – J. M. is a poor mathematician Nov 6 '11 at 6:08
  • $\begingroup$ What do you mean by product sum? If $x=6$, $a_1=2$, and $a_2=3$, do you allow the combination $2,3$ as well as $2,2,2$ and $3,3$? With the same $a_1$ and $a_2$ and $x=8$ do you allow $2,2,3$ (since $2\cdot 3+2=8$)? $\endgroup$ – Brian M. Scott Nov 6 '11 at 6:29
  • $\begingroup$ I'd say in general this is going to be difficult - but have a look at the Wikipedia page about partitions $\endgroup$ – Juan S Nov 6 '11 at 6:57
  • $\begingroup$ @Brian M.Scott Sorry for the confusion. That term 'product sum' was misleading. I've edited the question. $\endgroup$ – Andrew Nov 6 '11 at 6:58
  • $\begingroup$ @J.M. But please note that there's no exact closed range for the values of a1,a2,a3... Like, for example, it can be that x=18 and { a1=5, a2=3, a3=7, a4=13 }. $\endgroup$ – Andrew Nov 6 '11 at 7:43

Let $c(x)$ be the number of sequences that sum to $x$. How precisely do you need to know $c(x)$? These things tend to grow exponentially, so we should expect $c(10^{18})$ to have about a billion billion digits, up to some smallish factor. An exact answer will be practically impossible to compute. But you can possibly get at least the exact number of digits and the first few significant digits by this method:

Since the order of the term matters to you, the ${1,2}$ case is easy to solve: $c(x)$ is simply the $x+1$th Fibonacci number. You can see this because the last term in a sum totalling $x$ must be either $1$ or $2$, so therefore $c(x)=c(x-1)+c(x-2)$, which is the recurrence formula for the Fibonacci numbers. This agrees with your brute-force solution for $c(4)$, because $F_5=5$.

This suggests a general plan of writing down the linear recurrence that arises from your set of terms. In general the solutions of such a recurrence are linear combinations of exponential functions, whose bases are the roots of the characteristic polynomial. For large $x$ such as $10^{18}$, the term with the largest base will dominate all others completely, so we can just ignore all of the others. The trick is then just to find its coefficient.

One way to do this would be to set $c(x)=0$ for $-15\le x<0$ and $c(0)=0$, and then solve 16 linear equations in 16 unknowns.

Another way is simply to run the recurrence up to $c(N)$ for some $N$ between, say, 100 and 1000, and assume that by that time all of the smaller bases have faded into insignificance. Then we can estimate the coefficient as $\frac{c(N)}{r^N}$, and our approximation for large $x$ is $$\log c(x) \approx \log c(N) +(x-N)\log r$$ It is necessary to work with logarithms in this step, because even $c(1000)$ is likely to overflow the hardware floating-point representation in your computer. In fact, one could choose $N$ adaptively such that $c(N)$ is around $2^{500}$.

You can use $\frac{c(N)}{c(N-1)}$ as a first approximation of $r$ and refine it using Newton-Raphson iteration on the characteristic polynomial.

Special cases: If the numerically largest root of the characteristic polynomial is complex, the recurrence can have oscillating solutions that are never dwarfed by the exponential term. I think the only way this can happen is if the $a_i$s share a divisor $\ne 1$. So start by dividing out the greatest common divisor from the $a_i$s as well as from $x$.

If the largest root of the characteristic polynomial is a multiple root, the growth rates from the master theorem look slightly different. I think this cannot happen when the recurrence is constructed from your problem, but it is probably worth checking for explicitly when you have found $r$.

  • $\begingroup$ This would be very difficult to code. But thanks. $\endgroup$ – Andrew Nov 6 '11 at 18:52
  • $\begingroup$ Answer now rephrased so it would be more practical to code. $\endgroup$ – Henning Makholm Nov 12 '11 at 17:25
  • $\begingroup$ Henning, thanks a lot. But I was able to solve the problem by "Solving Linear Recurrences in Logarithmic time". Here's a link- fusharblog.com/… $\endgroup$ – Andrew Nov 16 '11 at 5:32
  • $\begingroup$ And yes, it would be impossible to get the exact answer for large values, I only needed to get the answer modulo a large prime no (10^9 + 7). $\endgroup$ – Andrew Nov 16 '11 at 5:36
  • $\begingroup$ It would have helped if you had told that before everyone tried to help you without this crucial information. If you need only the last digits, it's simple to work modulo $10^9+7$ (a smallish prime) and use exponentiation by squaring on the transition matrix of the linear recurrence. $\endgroup$ – Henning Makholm Nov 16 '11 at 11:16

Edited in the light of Byron's correction to the original:

The answer is the coefficient of $u^x$ in the expansion of $$\sum_{y=0}^x(u^{a_1}+u^{a_2}+\cdots+u^{a_r})^y$$ which can be helpful if there is something special about $a_1,a_2,\dots,a_r$ enabling you to simplify this expression; otherwise, it's just a rewording of your problem. But this means your problem is no easier than that of finding a particular coefficient in this expansion, which suggests that most of the time there is no method significantly better than brute force; it's just a question of how cleverly you can arrange for the force to be applied.

As for making it "solvable in a few seconds," you may be asking for too much. Let's look in some detail at a very small example of what you want to do: how many ways to get 100 with 2s, 3s, and 5s?

Well, there's one way using just 5s. You could use 17 5s and 5 3s; there are 22-choose-5 ways to do that. Or you could use 14 5s and 10 3s; 24-choose-10 ways. Carrying on, we see that if you use just 3s and 5s, there are $$1+{22\choose5}+{24\choose10}+\cdots+{32\choose30}$$ ways. Now there's a similar formula for using just 2s and 5s, and another one for just 2s and 3s. Now what if we use 2s, 3s, and 5s? We could use 19 5s, a 3, and a 2; that gets you a multinomial coefficient, 21-choose-19,1,1. Then there's a 22-choose-18,2,2, and there's a 23-choose-17,3,3 and a 24-choose-17,1,6 and so on and so forth. A simple formula? Maybe, but I don't see it. Although I'd be interested to see what Henning's method does with this example.

  • $\begingroup$ He treats zero differently from other numbers, so $2+2+0+0$ is the same as $0+0+2+2$. What he wants is the coefficient of $u^x$ in $\sum_{y=0}^x(u^{a_1}+\cdots +u^{a_r})^y$. $\endgroup$ – user940 Nov 6 '11 at 14:16
  • $\begingroup$ Can you give some computational insight into it. I need to write a code for the same. And I can't afford even a linear complexity since x can be as large as 10^18. So I think there must be some formula or something which makes it solvable in a few seconds. $\endgroup$ – Andrew Nov 6 '11 at 18:50
  • $\begingroup$ @Gerry You have to remove the "1+" under the power of $y$. Alternatively, summing over all $0\leq y<\infty$, the generating function is $1/(1-u^{a_1}-\cdots -u^{a_r})$. $\endgroup$ – user940 Nov 7 '11 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.