python - 欧拉项目 454 丢番汀 recipricols

Question

问题是：在以下等式中，x、y 和 n 是正整数。

1/x + 1/y = 1/n

对于极限 L，我们将 F(L) 定义为满足 x < y ≤ L 的解的数量。

我们可以验证 F(15) = 4 和 F(1000) = 1069。求 F(1012)。

我决定测试是否能找到 F(15)

count = 0
limit = 15
storage = []
x = 1
y = 1

for x in range(limit + 1):
    for y in range(limit + 1):
        x += 1
        y += 1
        n = x*y/(x+y)
        condition = x*y%(x+y)

        if (condition == 0 and x<y and y<limit):
            count += 1
            storage.append(x)
            storage.append(y)
            storage.append(n)

print (storage)
print (count)

但是列表中没有存储任何内容。

Answer 1

您正在循环x内部进行修改。循环之前y的x += 1属于。y您可以通过range()有效地使用来完全消除增量。range(1,limit+1)将从 1 开始。

你也没有比较y和limit正确。y <= limit.

您的程序稍作修改的版本：

count = 0
limit = 15
storage = []
x = 1
y = 1

for x in range(1,limit + 1):
    for y in range(1,limit + 1):
        n = x*y/(x+y)
        condition = x*y%(x+y)

        if (condition == 0 and x<y and y<=limit):
            count += 1
            storage.append(x)
            storage.append(y)
            storage.append(n)

print (storage)
print (count)

Answer 2

即使试图以 10^5 的速度计算，你也会用蛮力方法度过一段地狱般的时光。我也一直在想办法解决这个问题。

这是我所知道的：

1/x + 1/y = 1/n 可以改写为

1/(n+a) + 1/(n+b) = 1/n 这可以简化为 ab = n^2

（这是我用来解决问题 108 和 110 的方法）通过获取 n^2 的所有除数，您可以解决“a”和“b”，但这只有在 n 是固定整数时才真正有帮助。

我还没有弄清楚这将如何帮助我处理 454。