1 of 3

Algorithm for listing all solutions to a linear Diophantine equation.

Consider the linear Diophantine equation of the form: $$\sum_{i=1}^{k}a_ix_i=n.$$ My goal is to list all the non-negative solutions to this equation. I am trying to write a recursive algorithm, but I am not able to build the solution recursively. Here is what I have so far:

import math
def ListOfSolutions(n,L):
if len(L) == 1:
ak = L[0]
if n%ak == 0:
return [n//ak]
else:
return [None]

a1 = L[0]
ans = []
end = math.floor(n/a1)
for k in range(0, end + 1):
res = ListOfSolutions(n-k*a1,L[1:])
if None not in res:
ans.append([k] + res)
return ans

print (ListOfSolutions(5,[2,1]))


The algorithm works for a list of two coefficients $$[2,1]$$ but when I try $$3$$ or more I get errors. Perhaps someone could give me some indication as to what I am doing wrong here.

 asked Jan 2 '19 at 19:56 model_checker 15155 bronze badges