Representations of an integer as the sum of other integers

Question

Given a finite set $S$ of (distinct) integers $s_1, \dots, s_n$ and an integer $x$, I'm looking for all representations (where order is important) $$ x=\sum_{i=1}^ks_{t_i} (t_i\in\{1,\dots,n\}) $$

For example

1. $x = 4, S = \{1,2\}$: Five solutions. $$4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2$$

2. $x = 7, S = \{3,5\}$: No solution.

3. $x$ odd, all $s_i$ even: No solution.

_{This is for a photo gallery on a website and can easily be solved programmatically using recursion. However, it left me thinking about the theory, which may or may not help optimize the algorithm.}

Now, as a generalization of 3., it can be easily seen that there are no solutions when $$\gcd(s_1, \dots, s_n)\ne \gcd(x, s_1, \dots, s_n)$$

What other conclusions can we draw, particularly on the existence of solutions?

Is this problem known by a specific name? (Edit: yes, I'm looking for restricted partitions; related: Coin problem, Subset sum problem, Knapsack problem)

Answer 1

The problem of deciding whether there is a solution for $x$ and $S$ is difficult to characterize in general, but I do know a useful result in the special case where $|S| = 2$.

Theorem. If $S = \{m,n\}$ where $m,n$ relatively prime, then there is a solution for $x$ if and only if there is not a solution for $mn - m - n - x$.

Note that this easily generalizes to when $m,n$ are not relatively prime, because if $(m,n) = d > 1$, you can just consider $\frac{x}{d}$ and $S = \{\frac{m}{d},\frac{n}{d}\}$.

Proof. Note that there is a solution for an integer $y$ if and only if we can write $y$ as a sum of $m$s and $n$s, i.e. $y = am + bn$, where $a,b \ge 0$.

First, suppose towards contradiction that there is a solution for both $x$ and $mn - m - n - x$. Then adding the two solutions together gives a solution for $mn - m - n$. Thus we can write $mn - m - n = am + bn$. But this implies $a \equiv -1 \pmod n$ and $b \equiv -1 \mod m$, so $a \ge n-1$ and $b \ge m - 1$, so $$ mn - m - n = am + bn \ge (n-1)m + (m-1)n = 2mn - m - n, $$ a contradiction.

Therefore, it suffices to show that there is a solution for at least one of $x$ and $mn - m - n - x$. By the fact that $m$ and $n$ are relatively prime, we can find $a, b \in \mathbb{Z}$ such that $$ am + bn = x $$ Let $a \equiv a' \pmod n$ and $b \equiv b' \pmod m$, where $0 \le a' < n$ and $0 \le b' < m$. Then $$ a'm + b'n \equiv x \pmod {mn} $$ Let $a'm + b'n = x + kmn$, where $k \in \mathbb{Z}$. If $k \le 0$ we are done because $x = a'm + b'n + (-k)mn$ is a sum of $m$s and $n$s. Conversely, if $k > 0$, we write \begin{align*} mn - m - n - x &= mn - m - n - a'm - b'n + kmn \\ &= (n - 1 - a')m + (m - 1 - b')n + (k-1)mn \end{align*} and since $n -1 - a', m - a - b', k-1 \ge 0$, there is a solution for $mn - m - n - x$.

$$ * \quad * \quad * $$

A well-known corollary to this theorem is that there is always a solution for $x$ whenever $x > mn - m - n$, but not when $x = mn - m - n$.

$$ * \quad * \quad * $$

EDIT: The above theorem only applies when $m$ and $n$ are nonnegative.

• If exactly one of $m$ and $n$ is negative, then clearly there is a solution for any $x$ since there is a solution for $1$ and $-1$. I.e., write $am + bn = 1$ and $cm + dn = -1$ for $a,b,c,d \ge 0$, and then we have $(a|x|)m + (b|x|)n = |x|$ and $(c|x|)m + (d|x|)n = -|x|$. (This suffices since $x$ is equal to either $|x|$ or -|x|).

• If both $m$ and $n$ are negative, then the situation is basically the same as when they are positive. In this case, there is a solution for $x$ if and only if there is a solution for $-x$ using $S = \{|m|,|n|\}$.