更高效的Python for循環（3個冗餘環路）在迭代

Question

我想實現下面的代碼的較大值：

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循環來加速這個過程，或者也許有辦法在沒有循環的情況下做到這一點？

Answer 1

我要帶數學方法與計算機科學方法。減少這些循環顯然有一些有趣的問題，但數學方法可能會帶來幾乎相同的事情，並帶有一個小錯誤。

我想知道是否有這個序列的封閉形式公式，因爲這總是比任何循環都快！在您提供的OEIS鏈接，在公式中，有人提供的

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頁面上的其他評論：

Ceva定理用於從天真計數中扣除消失區域。對於n奇數，第一個推導是n = 15，對於n偶數，n = 20。

15和20碰巧是第一個與empirical分歧！所以似乎大部分時間實證生成函數都是正確的（「天真計數」？），但是當必須進行推論時，它在某些點上是一個上界。這是進入特定領域的領域，我不太瞭解Ceva的定理，以確切地知道何時以及如何進行這些推理 - 所以恐怕我無法改進這種封閉形式的上限，因爲我擁有它以上。

你原來的問題想測試10 ** 10。所以現在做int(empirical(10**10))瞬間：

299999999939999956992 

這可能是完全正確的，或上限這是非常，非常接近真正的答案。

我知道這是一個「替代」解決方案，但希望它是一個信息轉移。這就像有人要求你找到（10 ** 10）斐波那契數。你可以做循環，但如果存在一個封閉形式的公式，使用它！

Answer 2

操作(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 3）複雜度爲O（N²）