Reti43 has the right idea, but there's a quick recursive solution that works with less restrictive assumptions about your inequalities.
def solve(smin, smax, coef1, coef2):
"""
Return a list of lists of non-negative integers `n` that satisfy
the inequalities,
sum([coef1[i] * n[i] for i in range(len(coef1)]) > smin
sum([coef2[i] * n[i] for i in range(len(coef1)]) < smax
where coef1 and coef2 are equal-length lists of positive integers.
"""
if smax < 0:
return []
n_max = ((smax-1) // coef2[0])
solutions = []
if len(coef1) > 1:
for n0 in range(n_max + 1):
for solution in solve(smin - n0 * coef1[0],
smax - n0 * coef2[0],
coef1[1:], coef2[1:]):
solutions.append([n0] + solution)
else:
n_min = max(0, (smin // coef1[0]) + 1)
for n0 in range(n_min, n_max + 1):
if n0 * coef1[0] > smin and n0 * coef2[0] < smax:
solutions.append([n0])
return solutions
You'd apply this to your original problem like this,
smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 3)
solns7 = solve(smin, smax, coef1, coef2)
len(solns7)
1013
and to the longer problem like this,
smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 6, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 7, 3)
solns8 = solve(smin, smax, coef1, coef2)
len(solns8)
4015
On my Macbook, both of these cases are solved in milliseconds. This should scale reasonably well to slightly larger problems, but fundamentally, it's O(2^N) in the number of coefficients N. How well it actually scales depends on how large the additional coefficients are - the more large coefficients (compared to smax-smin), the fewer possible solutions and the faster it'll run.
Updated: From the discussion on the linked M.SE post, I see that the relationship between the two inequalities here is part of the structure of the problem. Given that, a slightly simpler solution can be given. The code below also includes a couple of additional optimizations, which speed up the solution for the 8-variable case from 88 milliseconds to 34 milliseconds on my laptop. I've tried this on examples with as many as 22 variables and gotten the results in less than a minute, but it's never going to be practical for hundreds of variables.
def solve(smin, smax, coef):
"""
Return a list of lists of non-negative integers `n` that satisfy
the inequalities,
sum([coef[i] * n[i] for i in range(len(coef)]) > smin
sum([(coef[i]+1) * n[i] for i in range(len(coef)]) < smax
where coef is a list of positive integer coefficients, ordered
from highest to lowest.
"""
if smax <= smin:
return []
if smin < 0 and smax <= coef[-1]+1:
return [[0] * len(coef)]
c0 = coef[0]
c1 = c0 + 1
n_max = ((smax-1) // c1)
solutions = []
if len(coef) > 1:
for n0 in range(n_max + 1):
for solution in solve(smin - n0 * c0,
smax - n0 * c1,
coef[1:]):
solutions.append([n0] + solution)
else:
n_min = max(0, (smin // c0) + 1)
for n0 in range(n_min, n_max + 1):
solutions.append([n0])
return solutions
You'd apply it to the 8-variable example like this,
solutions = solve(185, 205, (97, 89, 42, 20, 16, 11, 6, 2))
len(solutions)
4015
This solution directly enumerates the lattice points in the bounded region. Since you want all of these solutions, the time it takes to get them is going to be proportional (at best) to the number of bound lattice points, which grows exponentially with the number of dimensions (variables).
