Equation Involving Digit Sum Function

Question

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

Answer 1

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.