如何有效地找到一对数字，其中一个的平方等于另一个的立方？

Question

我需要找到(i,j)一个数字的对和对的数量N，以满足以下条件：1 <= i <= j <= N 并且 i * i * i = j * j。

例如，对于N = 50，对数为 3，即(1,1), (4,8), (9,27)。

N = 10000我尝试了下面的函数代码，但是对于大量类似或更多的数据来说，它花费了太多时间：

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

让是某个满足 的k整数的平方根，其中也是一个整数。由于是整数的平方根，因此是整数。从方程中我们可以解出等于，所以它也是一个整数。ii*i*i == j*jjkk*kjk*k*k

由于k*k*k是一个整数并且k*k是一个整数，因此将这两者相除k就是有理数。但是k是整数的平方根，因此它必须是整数或无理数。既然它是有理数，那么它一定是一个整数。

由于k是一个整数，因此所有解决方案都只是(k*k, k*k*k)针对整数k。由于我们将迭代k>=1，我们知道这一点k*k <= k*k*k，即i <= j，所以我们不必担心这一点。我们只需要在k*k*k达到时停止迭代即可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

即使是 100000 次，它也几乎可以立即运行N，无需 C 级优化。