我正在尝试实现以下代码：
def foo(n, p):
for i in range(1,n):
for j in range(1,n):
for k in range(1,n):
if ((n-j)*i*k)==(j*(n-i)*(n-k)):
p=p-11
但是 n 将接近 10^10 的值，这使得效率极低。事实上，即使 n=1000，这也很慢。
有没有办法通过压缩 for 循环来加速这一点，或者也许有一种方法可以在没有 for 循环的情况下做到这一点？
我将采用数学方法与计算机科学方法。减少这些 for 循环显然存在有趣的问题，但数学方法可能会让你得到几乎相同的事情，但有一个微小的错误。
我想知道这个序列是否有封闭式公式，因为它总是比任何循环都快！在您提供的 OEIS 链接中，在 FORMULA 下，有人提供了一个"经验"生成函数
x*(1+5*x+11*x^2+x^3+6*x^4)/(1-x)^3/(1+x)^2
我稍后会谈到"经验"部分。但是因为这是一个多项式的比率，所以如果你阅读了生成函数的工作原理，那么得到一个闭式解是相当容易的。如果这种方法最终成为您喜欢的方法，我可以将代数添加到我的答案中，但现在，让我们直接切入公式：
def empirical(n):
return ((-1)**n * (-1.5*n + 2.5)) +
(3.0*n**2 - 4.5*n + 3.5)
非常干净和简单。这有多准确？好吧，我检查了前 500 个值。这两个函数通常完美地排列在一起，但有时empirical夸大了真实的顺序：
correct empirical pct_diff
1 1 1.0 0.000000
2 6 6.0 0.000000
3 19 19.0 0.000000
4 30 30.0 0.000000
5 61 61.0 0.000000
6 78 78.0 0.000000
7 127 127.0 0.000000
8 150 150.0 0.000000
9 217 217.0 0.000000
10 246 246.0 0.000000
11 331 331.0 0.000000
12 366 366.0 0.000000
13 469 469.0 0.000000
14 510 510.0 0.000000
15 625 631.0 0.009600*
16 678 678.0 0.000000
17 817 817.0 0.000000
18 870 870.0 0.000000
19 1027 1027.0 0.000000
20 1080 1086.0 0.005556*
21 1261 1261.0 0.000000
22 1326 1326.0 0.000000
这种偶尔的差异几乎总是小于1%。现在，我不能保证这种模式会持续n = 10**10(即，经验几乎总是正确的，每隔一段时间就会略有夸大其词)，但请查看OEIS页面上的另一条评论：
切瓦定理用于从朴素计数中扣除消失区域。对于 n 个奇数，第一个扣除点为 n=15，对于 n 偶数，第一个扣除点为 n=20。
15和20恰好是与empirical的第一个分歧！因此，经验生成函数似乎在大多数情况下都是正确的("朴素计数"？)，但在某些地方，当必须进行推论时，这是一个上限。这进入了特定领域的领域，我对Ceva定理的了解还不够，无法确切地看到何时以及如何进行这些推论 - 所以我担心我无法改进这个封闭形式的上限，因为我上面已经有了它。
您最初的问题想测试 10**10。所以现在立即int(empirical(10**10))：
299999999939999956992
这要么完全正确，要么是一个非常非常接近真实答案的上限。
我知道这是一个"替代"解决方案，但希望这是一个信息丰富的转移。这就像有人让你找到(10**10)个斐波那契数。您可以执行循环，但如果存在闭式公式，请使用它！
操作(n-j)*i*k=j*(n-i)*(n-k).我们有j=n/(((n-i)*(n-k))/(i*k) + 1)，j 应该是 1 到 n-1 之间的整数，所以：
def foo(n, p):
for i in range(1,n):
for k in range(1,n):
j=n/(((n-i)*(n-k))/(i*k) + 1)
if n%(((n-i)*(n-k))/(i*k) + 1) == 0 and j > 0 and j < n:
p=p-11
这将复杂度从 O(n³) 降低到 O(n²)