CODEWITHSUNDEEP
pythonalgorithmmath
Talha Quddoos
Talha Quddoos

Reputation: 556

What's the efficient way for finding two numbers which match an equation for a specific result?

Referring to this answer to my question on StackExchange, what is the best and efficient way in Python to find the numbers which satisfy the following equation:

x = (2 ** a) * (3 ** b)

For example, if I have the number 40, and I have to find for what value of a and b, the value of x becomes 40?

Upvotes: 3

Views: 706

Answers (5)

jackw11111
jackw11111

Reputation: 1547

I don't believe an equation like that can be solved analytically because in an equation with two unknowns, you would only be solving one in relation to the other.

In short, if you equation is v = x^a*y^b you want to rearrange to solve for a, so that would be:

a = (log(v) - b*log(y)) / log(x)

but as you can see, it is defined in terms of b, which isn't given, so then we iterate through values of b, essentially guessing it, given the result of a.

To define what the search space is you would need to search up to an exponent value, e, such that:

(larger of x and y)^e = v

Here's an example implementation:

from math import log, ceil, fabs

def solver(x, y, v):
    # v = x^a*y^b and solving for a and b

    if (x > y):
        larger = x
    else:
        larger = y
    # figure out upper limit of exponents to search
    upper = ceil(log(v) / log(larger))

    solutions = []

    # loop through values up to upper bound
    for i in range(1, upper):

        # calculate first exponent
        a = (log(v) - i * log(y) ) / log(x)

        # early out for exponents that aren't integers
        if (fabs(a - round(a)) > 0.0001):
            continue
        # calculate second exponent from first, check if integer
        b = (log(v) - a * log(x) ) / log(y)

        if (fabs(b - round(b)) < 0.0001):
            # add to possible solutions
            solutions.append((round(a), round(b)))

    return solutions

print (solver(2, 3, 3888))  # [(4, 5)] ; that is, 2^4*3^5=3888
print (solver(2, 9, 46656)) # [(6, 3)] ; that is, 2^6*9^3=46656
print (solver(2, 3, 40))    # []       ; no solution

Upvotes: 0

Anuj
Anuj

Reputation: 1665

The equation you mentioned is called a Linear Diophantine equation. In brief, Linear Diophantine equation is an equation of the form:

ax + by = c

where a, b and c are given integers and we are only concerned with integer solutions of this equation.

We want to find if there is a solution to this equation, and if there is, what are those solution?

To generalize what Serge Ballesta answered, this Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b.

In order to find one of the solutions to the above problem (which will lead you to other solutions) one can use the Extended Euclidean Algorithm.

In brief, the extended version finds the GCD of two numbers a and b and a way to represent GCD in terms of a and b, i.e. coefficients x and y for which:

ax + by = gcd(a,b)

Moreover, if (x, y) is a solution, then the other solutions have the form:

(x + kv, y − ku)

where k is an arbitrary integer, and u and v are the quotients of a and b by the greatest common divisor of a and b.

Here is a link to the python implementation of Extended Euclidean Algorithm: https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended

Do visit the links I have provided in the solution if you want to learn more about Linear Diophantine Equation (or Diophantine Equation in general) and Extended Euclidean Algorithm.

Upvotes: 1

mugiseyebrows
mugiseyebrows

Reputation: 4698

If upper bound of x is fixed it may be efficient to precompute all possible solutions (where a in range 0..log(xmax,2) and b in range 0..log(xmax,3)) and store in memory (on disk) as x:(a,b) dictionary. For example all solutions for 64bit integers (up to 9,223,372,036,854,775,807) requires about 64*64*3*8 bytes of memory (about 100kb), so finding a,b will only require dictionary lookup.

Upvotes: 0

Serge Ballesta
Serge Ballesta

Reputation: 148890

It is a math problem.

If you want a and b to be integers, the equation can only have solutions if x is a multiple of 2 and 3 and of no other prime factor.

The solution is to find the exponents for 2 and 3 in the decomposition in prime factors of x (just divide x by 2 until it is no longer divisible, then by 3, and if something remains you will have no solution)

If you want a and b to be reals, you have an infinite number or solutions if x > 0. In fact you can choose a and find b as ln(x / (2**a)) / ln(3).

Are you sure of your formula?

Upvotes: 3

MLavrentyev
MLavrentyev

Reputation: 1969

This is a good problem to give to an SMT solver like Z3. For python, you can install bindings for it called Z3Py. Then, you can do something like this:

a = Int('a')
b = Int('b')
solve(40 == (2 ** a) * (3 ** b))

Another good resource to check out is here: https://ericpony.github.io/z3py-tutorial/guide-examples.htm.

Note that you can change a and b to be reals by using Real instead of Int. In this case, as @Damien mentions, this formula is unsatisfiable.

I should note, however, that this is not "efficient". SMT problems can be exponential in time complexity, and SMT is also undecidable (i.e. can't give you an answer for some problems). But that's just the nature of the problem you're trying to solve, unfortunately.

Upvotes: 0

Related Questions