How about checking the number of coins as a function of K%9? Then you can translate it to the function of log(K).
Let K%9 = r, i.e. there is an integer n such that K = 9n + r, and r is between 0 and 8 inclusive.
- r=0: we need n coins of value 9,
- r=1: we need n coins of value 9 + 1 coin of value 1 = n+1 coins
- r=2: we need n coins of value 9 + 2 coins of value 1 = n+2 coins
- r=3: we need (n-1) coins of value 9 + 2 coins of value 6 = n+1 coin, or 3 coins of value 1 if K=3
- r=4: we need n coins of value 9 + 1 coin of value 4 = n+1 coins
- r=5: we need n coins of value 9 + 1 coin of value 4 + 1 coin of value 1 = n+2 coins
- r=6: we need n coins of value 9 + 1 coin of value 6 = n+1 coins
- r=7: we need n coins of value 9 + 1 coin of value 6 + 1 coin of value 1 = n+2 coins
- r=8: we need n coins of value 9 + 2 coins of value 4 = n+2 coins
Proofs: For the case r=0: we know that we can do it with n coins. If we were using m coins, m < n, than the max total value is m * 9, 9 being the max value of the coin. But 9m is less than K=9n, so we cannot use m coins to get K
For the cases where we have r=1, r=3, r=4 and r=6: following the same reasoning as above, we know that n coins would be enough (9n < K, K being 9n +r), and we know how to do it with n+1 coins.
For the cases r=2, r=5 and r=8 For the total amount, K, K%3=(9n+r)%3=r%3=2; for the values of the coins, 6%3=0 and 9%3=0, but 1%3=1 and 4%3=1. Therefore, to get K we need at (2+3j) coins of values 1 or 4. Now we need to prove that, if we use n+1 coins, and at least 2 coins are of values 1 or 4, we cannot get K. Indeed, the max value of n+1 coins is 9*(n-1) + 2*4 = 9n-1, this is less than K=9n+r.
Finally, for the case r=7: Suppose we use n+1 coin. All of them is 9, we get 9*(n+1), this is not we want. If at least one of them is not 9, than the total value is at most 9n + 6, 6 being the second most valuable coins, this is not enough. Thus, n+1 is not enough. And we know how to get it with n+2. Voila!