How to efficiently find pairs of numbers where the square of one equals the cube of the other?

user_19476980 0
Viewed 107

I need to find the pairs (i,j) and number of pairs for a number N such that the below conditions are satisfied: 1 <= i <= j <= N and also i * i * i = j * j.

For example, for N = 50, number of pairs is 3 i.e., (1,1), (4,8), (9,27).

I tried the below function code but it takes too much time for a large number like N = 10000 or more:

def compute_pairs(N):
    pair = []
   
    for i in range (1, N):
        for j in range (i, N):
            print( 'j =', j)
            if i*i*i == j*j:
                new_pair = (i,j)
                pair.append(new_pair)
    print(pair)
    return len(pair)
nested-loops time-complexity python
2 Answers

Let k be the square root of some integer i satisfying i*i*i == j*j, where j is also an integer. Since k is the square root of an integer, k*k is integer. From the equation, we can solve that j is equal to k*k*k, so that is also an integer.

Since k*k*k is an integer and k*k is an integer, it follows by dividing these two that k is rational. But k is the square root of an integer, so it must be either an integer or irrational. Since it is rational, it must be an integer.

Since k is an integer, all the solutions are simply (k*k, k*k*k) for integer k. Since we will iterate over k>=1, we know that k*k <= k*k*k, i.e. i <= j, so we don't have to worry about that. We just have to stop iterating when k*k*k reaches N.

from itertools import count # unbounded range; we will `break` when appropriate
def compute_pairs(N):
    result = []
    for k in count(1):
        i, j = k*k, k*k*k
        if j >= N:
            break
        result.append((i, j))
    return result

This runs almost instantaneously even for N of 100000, no C-level optimization needed.

user_5236120

Think about the problem. You need i cubed to be the same as j squared?

We know that pairs like (0, 0), (1, 1), (4, 8), and (9, 27) satisfy this condition.

What do 0, 1, 4, and 9 all have in common?

They're 0, 1, 2, and 3 squared.

What then do 0, 1, 8, and 27 all have in common?

They're the same numbers cubed.

Once you realize the pattern, the answer can be calculated in extremely short time.

user_152613150
Related