項目歐拉＃23數學

我使用Mathematica解決Problem 23 of Project Euler：項目歐拉＃23數學

查找不能寫成兩個充足數的和所有的正整數的總和。

回想一下，豐富的數字#就是這樣一個這樣的Total[Divisors[#]] - # > #。這裏是我的代碼：

list1 = Table[i, {i, 1, 28123}]; 
list2 = Select[list1, Total[Divisors[#]] - # > # && 2 * # < 28123 &]; 
list3 = {}; 
l = Length[list2]; 
For[i = 1, i <= l, i++, 
For[j = i, j <= l, j++, 
    list3 = Append[list3, list2[[i]] + list2[[j]]]]]; 
Total[Complement[list1, list3]]

這是非常緩慢;嵌套的For循環會花費大量時間進行評估。

我正確接近這個問題嗎？有沒有辦法讓它更快？

編輯：28123背後的原因是任何大於它的數字都可以寫成兩個豐富數字的和。

來源

2012-12-18 Raptor

用你的替換你的循環來創建list3。

list3 = (list2[[#]] + list2[[# ;; -1]]) & /@ Range[Length[list2]] // Flatten;

定時給我的舊電腦

更新

上0.49秒接聽抱怨項目list3作爲構建在我的答案給出錯誤的解決方案。

好吧。它給出了與使用原始代碼的list3構建相同的內容。這種方法更快。如果原始方法中的構造是錯誤的，那麼我真的不能做任何事情，因爲問題是如何使它更快，而不是正確的算法本身的任何錯誤，這是我不熟悉的。假設是發佈的算法是正確的，但速度很慢。

(*28123 replaced with smaller value to check, else will take forevever*) 
(*for original algorithm to finish *) 

n = 200; 
list1 = Table[i, {i, 1, n}]; 
list2 = Select[list1, Total[Divisors[#]] - # > # && 2*# < n &]; 
list3 = {}; 
l = Length[list2]; 
For[i = 1, i <= l, i++, 
    For[j = i, j <= l, j++, 
    list3 = Append[list3, list2[[i]] + list2[[j]]]]]; 


mylist3 = (list2[[#]] + list2[[# ;; -1]]) & /@ Range[Length[list2]] //Flatten;

比較

list3 - mylist3

Mathematica graphics

來源

2012-12-18 05:04:44 Nasser

這是快如閃電，但給出了不正確的解決方案。 – Raptor

我很抱歉！我只是意識到我犯了一個邏輯錯誤。我使用更快的建議來修復它。謝謝！ – Raptor

（28123替換爲更小的值來檢查，否則將採取forevever）

我會避免在循環Mathematica除非你別無選擇。我用上述解決方案殺死了Kernel，因爲它似乎需要很長時間才能完成。

下面的解決方案在我的Macbook上需要大約6秒。您可以將其上限設置爲20161，正如其他人在歐拉論壇中指出的那樣。

Total[Complement[Range[20161], 
     Plus @@ # & /@ 
     Tuples[Select[Range[20161], ((DivisorSigma[1, #] - #) > #) &], 2]]]

更新：

閱讀優化的一些其他線程，我發現，與Total[#]&刮鬍子了另一個第二更換

Plus @@ # &。

這個版本需要4.9秒

Total[Complement[Range[20161], 
     Total[#] & /@ 
     Tuples[Select[Range[20161], ((DivisorSigma[1, #] - #) > #) &], 2]]]

來源

2015-12-22 17:53:16 ejkitchen

項目歐拉＃23數學

回答

相關問題