Algorithm to find if a number is sum of multiples of other numbers

Question

I have three numbers 6,9,20. For a given number I need to check if it can be equal to the sum of multiples of these three numbers. For Ex: n = 47 then it can be determined that 47 = 9*3 + 20

n=23 then there cannot be no combinations.

It can be determined in o(n^3). But is there a better way to do it ?

Answer 1

This is a Linear Diophantine Equation.

If the coefficient can be negative, then check Bézout's identity:

If the sum is a multiple of the gcd of the numbers, then there's a solution.

In your example gcd=1, so there's a solution for any sum. So I guess you're looking for non-negative coefficents.. :(

Answer 2

I think I have a solution for You(only if coefficients can be 0).

Sum of multiples of 6 and 9 are all the multiples of 3 (except the 3 itself). So We can say, we need to check if a number equals to 3*k + 20*l.

So, if You've got a number n,

• if n is multiple of 3, there is a decomposition and we can find it simple(if n is even, it is x*6 , if it is odd, it is 9+x*6
• if n is not a multiple of 3, decrease by 20 until it will be, than go to the first step. If You go below 0 and still didn't find a multiple of 3, there's no solution.
• there is at least one solution for every n > 60

Be careful with 23 and 43, since 3 can not be written that way, 23 and 43 can neither.

Why should this work? Because 20 mod 3 = 2, 40 mod 3 = 1 , 60 mod 3 =0. So after decreasing by 20 at most 2 times, You will find a multiple of 3 that can be solved easily.