1

私はMathematicaを使ってプロジェクトオイラーの問題23を解いています：

2つの豊富な数の合計として書くことができないすべての正の整数の合計を見つけます。

#豊富な数はそのようなものであることを思い出してください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は、それより大きい任意の数が2つの豊富な数の合計として記述できるためです。

4

2 に答える 2

4

list3を作成するループをこれに置き換えます。

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

古いPCではタイミングが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グラフィックス

于 2012-12-18T05:04:44.990 に答える
2

（28123は、チェックするために小さい値に置き換えられます。それ以外の場合は、永遠にかかります）

他に選択肢がない限り、Mathematicaのforループは避けたいと思います。完了するまでに非常に長い時間がかかるようだったので、上記のソリューションでカーネルを強制終了しました。

以下の解決策は私のMacbookで約6秒かかります。他の人がオイラーフォーラムで指摘しているように、上限を20161に設定できます。

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

アップデート：

最適化に関する他のスレッドを読んで、私は

Plus @@ # &もう1秒Total[#]&剃ります。

このバージョンは4.9秒かかります

Total[Complement[Range[20161], 
      Total[#] & /@ 
         Tuples[Select[Range[20161], ((DivisorSigma[1, #] - #) > #) &], 2]]]
于 2015-12-22T17:53:16.133 に答える