Decide if the number satisfies the underdetermined equation

Question

Is it possible to theoretically solve the spatial and temporal complexity using O (1), is the known positive integer K a solution to the equation

where a and b are fixed, positive integers (not multiples of another), and & mu; _i s are unknown non-negative integers, all but a finite number of which (but not all) are equal to zero? If this is not possible in O (1) space and time, what are the space and time requirements for the best-known algorithm?

The only approach to this problem that I have found is to list a subset of all possible K ‌ s ahead of time, but, of course, this requires me to select the upper cut-offs M and N such that I & le; N and? Forall; & mu; _i & le; M. Worse, its need for O (M ^N ) space, which is likely to be so huge that the search algorithm will not achieve O (1) output performance on real hardware. I have a bad feeling that this is actually a “Backpack Problem,” but I'm not sure if that’s not all. / p>

I am trying to get to O (1) both in space and in time, because I need to know if this can be done in real time in an embedded environment with a barely noticeable margin in the processor or RAM.

I don’t need to know the satisfying set of & mu; _i .

EDIT:. This Python function computes a given object S such that K in S is true if and only if K is one of the solutions to the above equation, given a, b and slices M and N, as described above.

 def compute_set(a, b, M, N): ss = [a*i + b for i in xrange(1,N+1)] aa = itertools.product(xrange(0,M+1), repeat=N) rv = set(map(lambda a: sum(a[i]*ss[i] for i in xrange(N)), aa)) rv.remove(0) return rv 

Answer 1

Decide in two steps.

At the first stage, calculate the description of the set {(x, y): x, y in Z and ax + by = K} using standard processing methods for the Diophantine equations . Let g = gcd (a, b); if g does not divide K, there are no solutions. Calculate g through the advanced Euclidean algorithm to solve ax '+ by' = g, and also calculate g; the first solution is (x ', y') * K / g. Other solutions are additively integer multiple (-b / g, a / g).

In step 2, calculate the description (x, y) of the solutions that can be achieved using different μ _i options. Since K ≥ 0, we know that y ≥ 1 is a necessary condition. If n is a variable, then x ≥ 0 and y ≥ 1 is a necessary and sufficient condition (put μ ₀ = y - 1 and μ _x = 1, and all the rest μs to 0).

If n is a parameter, then everything is a bit sticky. Using the results of stage 1, we find a solution (x, y) with x ≥ 0 and y maximum (if there is no such solution, then K is impossible). For this solution, check if x / y ≤ n.

 def egcd(A, B): """Returns a triple (gcd(A, B), s, t) such that s * A + t * B == gcd(A, B).""" a, b, s, t, u, v = A, B, 1, 0, 0, 1 while True: assert s * A + t * B == a assert u * A + v * B == b if not b: break q, r = divmod(a, b) a, b, s, t, u, v = b, r, u, v, s - q * u, t - q * v return a, s, t def solvable(K, a, b): g, s, t = egcd(a, b) q, r = divmod(K, g) if r: return False x, y = s * q, t * q assert a * x + b * y == K d = a // g q, r = divmod(y, d) if r <= 0: q -= 1 r += d assert 0 < r <= d x, y = x + q * (b // g), r assert a * x + b * y == K return x >= y