I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm trying to figure out how the combos work (I think this is a form of number theory).
For example, for a sum of 10 and using a universe of [4, 2, 1], I get (I'm showing how I perceive the breakdown):
2 * 4 + 1 * 2 + 0 * 1 = 4 + 4 + 2
2 * 4 + 0 * 2 + 2 * 1 = 4 + 4 + 1 + 1
1 * 4 + 3 * 2 + 0 * 1 = 4 + 2 + 2 + 2
1 * 4 + 2 * 2 + 2 * 1 = 4 + 2 + 2 + 1 + 1
1 * 4 + 1 * 2 + 4 * 1 = 4 + 2 + 1 + 1 + 1 + 1
1 * 4 + 0 * 2 + 6 * 1 = 4 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 + 5 * 2 + 0 * 1 = 2 + 2 + 2 + 2 + 2
0 * 4 + 4 * 2 + 2 * 1 = 2 + 2 + 2 + 2 + 1 + 1
0 * 4 + 3 * 2 + 4 * 1 = 2 + 2 + 2 + 1 + 1 + 1 + 1
0 * 4 + 2 * 2 + 6 * 1 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 + 1 * 2 + 8 * 1 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 + 0 * 2 + 10 * 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
So as the numbers get larger, I am having problems scaling it (if I have a sum of 1000 with 30 variables, it take forever). So looking at the problem like I have above, I thought I could break down the result based. So what I do is take the universe list [4,2,1] and go through the list and see how many of the previous numbers takes to make that number. Here's an example:
2 [[1, 1]]
4 [[2, 2]]
4 [[2, 2]]
What that means is 1+1=2, 2+2=4, so I can use that table to break down the first highest result (4+4+2… I look up the table and see that 2 = 1+1 so I replace that, then go back to the first highest result and then lookup the breakdown of the second number, etc.). I'm not sure but I believe this can scale because I can split the calculation and lookups over separate CPU/systems/clusters/etc..
There's probably many logical flaws, but the one I noticed right now is what if the number is a prime number or doesn't break down into the last highest number? Say my universe changes from [4,2,1] to [4,3,2,1]… because the highest match is still 4+4+2, the 3 will get missed totally as a solution.
So I'm wondering how I can mathematically deal with prime numbers (I have a function to identify them)? Also what is the correct logic if I have numbers that don't divide cleanly into each other? (universe of [6,4,2,1] breaks down also). In the past I brute forced this (try all until successful) the problem is, if I can't break down the problem into smaller math problems than I can't scale it. I think this can be done because I can scale it (on a small scale :-), but dealing with specific numbers are the problem (prime and I guess numbers that are the opposite of the sum odd or even).
Sorry for the long question and again, sorry if this is not appropriate for this Q/A but any suggestion or advice would helpful.
Best Answer
Ah, here we go: this one's the problem of enumerating the number of ways to make change. This problem has been discussed before on this site and in a nice textbook, but let's specialize to your problem.
Consider a country, Lost-soulia, where the currency unit is the Lostie. The existing coins of the realm have the values of 1 Lostie, 2 Losties, and 4 Losties. You're asking how many ways can one have 10 Losties in the coins of the realm.
One way to solving this makes use of the concept of generating functions; specifically, consider the generating function
$$\frac1{(1-a x)(1-b x^2)(1-c x^4)}$$
where $a,b,c$ each correspond to the number of each denomination. To solve your problem of representing 10 Losties in coins, we expand the generating function as a Maclaurin series, and take the coefficient of $x^{10}$. For this case, the required coefficient is
$$a^{10}+a^8 b+a^6 b^2+a^6 c+a^4 b^3+a^4 b c+a^2 b^4+a^2 b^2 c+a^2 c^2+b^5+b^3 c+b c^2$$
We count twelve terms in this result, corresponding to your twelve ways of representing 10 Losties in terms of Lostie coins. Each term can be interpreted as a particular partition of 10; for instance, the term $a^4 bc$ corresponds to having 4 1-Lostie coins, 1 2-Lostie coin, and 1 4-Lostie coin, which totals to 10 Losties. (The exponents of the $a,b,c$ correspond to the counts of each coin.)
We can generalize. If for instance Lost-soulia decides to release a brand spanking new 3 Lostie coin, you just need to change your generating function to
$$\frac1{(1-a x)(1-b x^2)(1-c x^4)(1-d x^3)}$$
where $d$ corresponds to the count of 3-Lostie coins.The coefficient of $x^{10}$ in the series expansion is
$$\begin{split}a^{10}+a^8 b+a^7 d+a^6 b^2+a^6 c+a^5 b d+a^4 b^3+a^4 b c+a^4 d^2+a^3 b^2 d+a^3 c d+a^2 b^4+\\ a^2 b^2 c+a^2 b d^2+a^2 c^2+a b^3 d+a b c d+a d^3+b^5+b^3 c+b^2 d^2+b c^2+c d^2\end{split}$$
which has 23 terms, so you have 23 ways of having 10 Losties in coins. The $abcd$ term for instance corresponds to partitioning 10 as $1+2+4+3$, and $ab^3 d$ corresponds to partitioning 10 as $1+2+2+2+3$.
I gave a short Mathematica routine for the change-making problem in the comments, but that version has a bug (try
MakeChange[8, {2, 7}]). Here is a more robust version of that routine:Much later: It turns out that the functionality of
MakeChange[]is already done by the intrinsic functionsIntegerPartitions[]andFrobeniusSolve[]. Still, I think the routine is a nice illustration of generating functions...There are more efficient methods for solving the Frobenius problem, using methods from graph theory and integer programming; you can search the web for papers discussing these methods for generating and counting integer partitions.