找到立方体等于平方的数字对

Question

给定一个数字 N，我们必须找到 i 和 j 对，其中 i^3=j^2

例如，让 N=50 因此我们将有 3 对 (1,1),(4,8),(9,27) 基本上，我们必须找到一对，其中一个数的立方与给定对中另一个数的平方相同

约束是

1<=N<10^6
1<=i,j

朴素的方法使用 2 个 for 循环遍历每个元素并得到立方体等于总和的那些对，时间复杂度为 O(n*2)

def get_pair(N):
    for i in range(1,N):
        for j in range(1,N):
            if i*i*i==j*j:
                print(i,j)
N=50
get_pair(N)

以更好的时间复杂度解决此问题的最佳方法是什么？

Answer 1

另一种天真的方法可能是使用“基本”值？

def get_pair(N):
    for i in range(N):
        if(i**3 > MAX):
            break    # Limit to the max you want, and i**3 > i**2 if i > 1

        print(i**2, i**3)

时间复杂度好像是O(n)（不是专家，错了请指正）

这样做是为了让第一个元素的立方 == 第二个元素的平方：

first = a^2
second = a^3

first^3 = a^(2*3) = a^6
second^2 = a^(3*2) = a^6

Answer 2

如果您知道 (x, y) 对总是 y = x * i，您可以使用一个循环（和最少的迭代）来执行此操作，这意味着您可以使用：

def get_pair(N):
    i = 1
    a = 1
    while a * i < N:
        b = a * i
        print(a,b)
        i += 1
        a = i**2

N=50
get_pair(N)

这得到所有 3 对：

1 1
4 8
9 27

总共只有 3 次迭代。

Answer 3

您可以使用itertool's combinations_with_replacement功能。

from itertools import combinations_with_replacement as combinations

def get_pair(N):
    for i, j in combinations(range(1,N), 2):
        if i*i*i==j*j:
            print(i,j)
N=50
get_pair(N)

Answer 4

由于您使用的是整数，如果在 1 和 N 之间存在某个数字 M = i^3 = j^2 对于 i 和 j，则意味着存在一个 k 使得 M = k^6。要找到 i 和 j，只需比较 M 的表示：

(1) M = k^6 = i^3 = (k^2)^3 因此 i = k^2

(2) M = k^6 = j^2 = (k^3)^2 因此 j = k^3

因为j总是大于或等于i，你只需要检查是否1 < k^3 < N。换句话说，k应该小于N的立方根。

k	M = k^6	i = k^2	j = k^3
2	64	4	8
3	729	9	27
4	4,096	16	64
5	15,625	25	125
6	46,656	36	216
...	...	...	...
97	8.329x10^11	9409	912,673
98	8.858x10^11	9604	941,192
99	9.415x10^11	9801	970,299

请注意，100 不是 k 的有效候选值，因为这会使 j 小于或等于 N 而不是 严格小于 N（如果我们使用 N = 10^6）。

因此，要获得满足您的问题的元组列表，请找到 k 的值，使得 1 < k^3 < N 和 return 元组中的平方和立方。

import math
from typing import List, Tuple

N: int = 10**6
pairs: List[Tuple[int, int]] = [(k * k, k * k * k) for k in range(2, math.ceil(N**(1 / 3)))]
print(pairs)

这是一个列表理解，shorthand 对 for-loop。

我基本上是在要求 Python 生成索引 k 上的元组列表，该索引 k 落在定义为 range(2, math.ceil(N**(1 / 3)) 的范围内。该范围恰好是上面 table 的第一列。

然后，对于该范围内的每个 k，我创建一个元组，其中第一项是 k^2，第二项是 k^3，就像 table 的最后两列一样。

也将 typing 库放入其中以备不时之需。清晰的代码是好的代码，即使对于这么小的东西也是如此。 Python 可以弄清楚 pairs 是一个元组列表，没有人告诉它，但是通过这种方式，我明确强制该变量是一个元组列表，以避免在有人试图给它时造成任何混淆不同的值或不确定变量包含什么。

找到立方体等于平方的数字对

find pairs of numbers where cube is equal to square

python

algorithm

data-structures