Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this 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
1  
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
    
This article seems to address precisely this problem. –  deinst Sep 24 '11 at 2:28
    
Thanks @deinst! –  Ted Sep 24 '11 at 5:01
add comment

1 Answer 1

I can't add comments (yet) due to having too few points, so I'll have to write an answer instead. The change making problem was mentioned above which is part of a larger family of problems called knapsack problems and they are usually NP-hard (the super increasing knapsack is e.g. one exception). I would look at algorithms for knapsack problems as they might give you ideas. Here's a good starting point:

http://en.wikipedia.org/wiki/List_of_knapsack_problems

These are usually solved by using some kind of a dynamic programming approach.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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