How can I reduce a number?

Question

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.

Answer 1

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:

MakeChange[n_Integer?Positive, v_?VectorQ] := Module[{l = Length[v], x}, 
   Exponent[#, Array[C, l]] & /@ 
    Flatten[{Expand[
        SeriesCoefficient[1/Apply[Times, 1 - Array[C, l] x^v], 
          {x, 0, n}]] /. Plus -> List}]] /;
VectorQ[v, (IntegerQ[#] && Positive[#]) &]

---

Much later: It turns out that the functionality of MakeChange[] is already done by the intrinsic functions IntegerPartitions[] and FrobeniusSolve[]. 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.

Answer 2

I will use the statement of the problem as user3296 gave it: "Write a computer program which, given a positive integer $n$ and a list of positive integers $S = \{m_1, m_2, \ldots, m_k\}$ as input, produces a list of every way of writing the number $n$ as a sum of elements of $S$."

The trick to solving many problems of this type is to break each case down exactly into smaller cases. For this particular problem, we can break down each problem involving a universe into multiple problems involving the next smaller universe, and that one into multiple problems involving the next smaller universe, and so on, until the universe is empty. With an empty universe, there's only one number we can make: 0.

More formally, to solve this problem, we use recursion on $S$. Consider the first element of $S$, $m_1$, and assume that the problem has already been solved for $\{m_2, m_3, \ldots, m_k\}$. If $n \ge m_1$, then we can use it once. Whether or not $n \ge m_1$, we can ignore $m_1$ and move on to the next element of the universe.

In pseudocode, our recursive function looks like this:

findSums(n, S) (if S is not empty):
    Start with an empty list, L, of sums.
    Is n greater than or equal to m1?
        If so, add all elements of findSums(n - m1, S) to L,
        and then put "m1 +" in front of each element of L.
    Add all elements of findSums(n, S \ m1) to L.
    We are done.  Return L.

findSums(n, emptyset) (if n is not 0):
    Return the empty list.
    (There is no way to add elements of the empty set
    to get something positive.)

findSums(0, emptyset):
    Return the list containing only the empty sum.

In Haskell:

findSums n (s:ss) =
    (if n >= s then map (s:) (findSums (n-s) (s:ss)) else [])
    ++ sums n ss

findSums 0 [] = [[]]

findSums _ [] = []