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

Question

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)

Answer 1

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.