# Equation Involving Digit Sum Function

Define the digit sum $$S$$ of a number as the sum of its digits. For example, $$S(456)=4+5+6=15$$. Given positive integers $$a_1, \cdots, a_n$$ and $$Q$$, I'd like to ask how to obtain the nonnegative solutions to $$S(\sum_{i=1}^{n} a_ix_i)=Q$$ which minimize $$\sum_{i=1}^{n}x_i$$.

## 1 Answer

Unless the $$a_i$$ are large and the $$x_i$$ are small where rounding issues intervene, you want the sum to be the minimum number whose sum of digits is $$Q$$. That will be a series of $$9$$s with a prefix digit for the remainder of dividing $$Q$$ by $$9$$. Let $$k=\lfloor \frac Q9 \rfloor, m=Q \bmod 9$$. Then $$N=(m+1)10^k-1$$ is the smallest number with sum of digits $$Q$$. We therefore want the solution to $$\sum_{i=1}^{n} a_ix_i=N$$ that minimizes $$\sum_{i=1}^{n} x_i$$. This is a classic linear optimization problem. Again, absent some strange things with the $$a_i$$, we will want to find the greatest $$a_i$$ and make $$x_i$$ large, then fix any rounding problem.