# Minimal solutions to $\sum a_i x_i = d$

Let $S = \{a_1, a_2, \ldots, a_n\}$ be a finite set of positive integers with $\gcd(a_1, a_2, \ldots, a_n)=1$, and let $d$ be any positive integer. Then $\sum_{i=1}^n a_i x_i = d$ is solvable in integers $x_i$.

1. How can I find a solution which minimizes $\sum |x_i|$ ?

2. (A more vague question.) Let $f(S, d)$ be the minimum possible value of $\sum |x_i|$; what can be said about this function as $S$ and/or $d$ vary? (An obvious observation is that $f(T,d) \le f(S,d)$ if $S \subset T$.)

When $n=2$, it's easy to answer. For $d=1$, the usual Euclidean algorithm gives a minimal solution. Equivalently, if the integers are $p$ and $q$, find the simple continued fraction expansion for $p/q$ that does not end in a 1. Then take the numerator and denominator of the second-to-last partial quotient, with appropriate choice of signs. You can check that this is minimal.

For $n=2$ and larger $d$, first solve for $d=1$ as above, then multiply the solutions by $d$. Now you have a solution to $p x_1 + q x_2 = d$, and all other solutions are given by $x'_1 = x_1 + kq$ and $x'_2 = x_2 - kp$, and you can easily find the right integer $k$ to minimize $|x_1|+|x_2|$. There may be a better way to do this.

The motivation (this is kind of bizarre, feel free to skip) is the following idealized product design scenario. You are designing controls for a robot that walks along the integers. Your controls consist of $n$ levers which can be pulled either to the left or right, and associated with each lever is a positive integer $a_i$. Pulling a lever moves the robot in that direction by a distance of $a_i$. You could just supply one lever with $a_1=1$, and the robot could reach any integer, but if some customer's application frequently needs to hop 15 spaces, they'll have to pull the lever 15 times which they won't like. So if a customer gives a certain set of preferred $d$ values, maybe even with a weighted frequency for each $d$, you want to choose an appropriate $S$ to keep $\sum |x_i|$ smaller for the more common $d$'s (that's the number of times the customer must pull the levers to achieve $d$). But you also want to keep $n$ small since that's cheaper and the customer wouldn't like having tons of unnecessary controls to remember. There's still some more to specify to get a precise question, but I hope this gives the gist of the motivation (maybe a precise version can become a separate question).

-
This seems like the change making problem, with the "twist" that the coefficients are allowed to be negative. The nonnegative version I linked to is NP-complete. I am not sure whether your problem is easy or hard. – Srivatsan Sep 23 '11 at 5:50
The vectors $x$ such that $a\cdot x=d$ form a lattice and your problem is closely related to the closest point in a lattice problem. The LLL algorithm is the approximate analog to the euclidean algorithm in higher dimensions for this problem. – deinst Sep 23 '11 at 15:13