Smallest sum of digits of a multiple of n

[el matematico]

A problem I've been thinking about for some time: Let s(n) be se sum of digits of n in base 10. It only adds once, so s(78)=15 and does not reduce further to 6 (it's not classes of equivalence modulo 9). For a given n, what's the smallest number in the infinite set S={s(n), s(2n), s(3n),...}?
Now, there are some obvious answers. If the prime divisors of n are restricted to {2,5}, the answer is 1, as there will be powers of 10 in S. If n is multiple of 3 but not 9, the smallest answer is a multiple of 3, most likely 3 itself. If it's a multiple of 9, the answer is a multiple of 9, possibly 9 itself.
But consider numbers that are coprime with 2, 3, 5. The answer for a lot of them is 2, if the equation 10^k ≡ -1 (mod n) has a solution. But what if it doesn't? The next posibility would be 3. Is there a way to guarantee that such a multiple exist? I don't think so, but also haven't proved either way. I think there is no bound for the smallest set of S, mainly because of the (posible) existence of arbitrarily large prime repunits and my lack of imagination on how to reduce the sum of digits of their multiples.
I've also been thinking ways to restrict the choice of n in a way that the answer becomes simple but not obvious (basically I think it's an interesting concept and would like to make nice problem out of it).

[eta oin shrdlu]

Here are a couple of hints, which I think lead to a proof that min S(n) is unbounded:

A number with digit sum d can be written 10^a(1) + ··· + 10^a(d). So the set of all numbers with digit sum d, modulo n, is (almost; see caveat below) the "sum set" d*T = T + T + ··· + T (mod n), the set of all sums of d elements chosen (with replacement) from the set T = {10^a mod n} of all powers of 10, modulo n. You are interested in finding values of n and d for which 0 is not in d*T.

[Caveat: for d>=10, d*T includes some elements with a smaller digit sum, because of carrying. But it still includes all of the elements with digit sum d.]


The set T has r = ord(10,n) elements (r the multiplicative order of 10, modulo n), so the sum set d*T has something less than r^d distinct elements (in fact at most C(r+d-1,d-1)). So if r and d are small enough, then very few of the numbers modulo n are in d*T, and it's highly likely that 0 is not.


An obvious choice of n would be a large factor of 10^a-1, for which T={1,10,100,...,10^a-1}, having only a elements. So for example with n=11111, the numbers with digit sum 4 are in 4*T, which has only 5⁴=625 elements, much smaller than n. In fact for this n it's easy to write down all of the elements of 4*T; T={1,10,100,1000,10000}, so we just write down all of the at-most-5-digit numbers with digit sum 4, and that's all. Clearly none of these is a multiple of n (and so none is congruent to 0); so 11111 has no multiples with digit sum 4.

[el matematico]

Yeah, I think I also proved that the sum of digits of any multiple of n=111..1 is at least the nunber of digits of n it in a not so formal way. I thought of using this as an upper bound for a general number, since any number coprime with 2, 3 and 5 has a (least) multiple like that. However, turns out this bound is abysmal, as it's the same as the period in the repeating decimal expansion of 1/n. Most of the time it's better to just take S(n) as an upper bound, which is already a pretty bad bound most of the time.