PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 87 / 3つの素数のべき乗

素数の2乗と3乗と4乗の和で表される最小の数は28である。50未満のこのような数はちょうど4つある。

  • 28 = 2^2 + 2^3 + 2^4
  • 33 = 3^2 + 2^3 + 2^4
  • 49 = 5^2 + 2^3 + 2^4
  • 47 = 2^2 + 3^3 + 2^4

50,000,000未満の数で素数の2乗と3乗と4乗の和で表される数は何個あるか?

Problem 87 - Project Euler


条件が「和が5*10^7未満」と単純なので単純計算で解けます。

まず,素数のしぼりこみ。2乗,3乗,4乗される素数の候補は順に908, 73, 23個でした。


和が5*10^7未満のものを抽出して,ダブリを除けば出来上がり。

Project Euler 50 / 連続する素数の和

素数41は6つの連続する素数の和として表せる。

41 = 2 + 3 + 5 + 7 + 11 + 13

100未満の素数を連続する素数の和で表したときにこれが最長になる。

同様に連続する素数の和で1000未満の素数を表したときに最長になるのは953で,21項を持つ。100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

Problem 50 - Project Euler


我ながら地道に解いてしまった。

f, g, h はこういう関数です。

  • f[i,j]:i番目の素数からj番目の素数までの和
  • g[i]:i番目の素数からはじめた場合,「和が10^6未満」の条件で最大何番目の素数まで足せるか
  • h[i]:i番目の素数からはじめた場合,「和が素数」の条件で最大何番目の素数まで足せるか

100万以下のすべての素数について調べると,約1分かかります。ただ,後ろの方の素数からはじめた場合,あっという間に和が100万を越えてしまうのでそう何個も足せないはずです。そういう数についても調べるのは無駄なので,n の候補をしぼりこむことにしました。

最初の素数である2からはじめた場合,h[1]=536番目の素数まで足せるので g[n] - n >= h[1] - 1 をみたす n について調べれば十分です。その数 nmax=11 個。
100万以下の素数は PrimePi[10^6]=78498 個ですから,計算量を大幅に減らせます。

答えは4番目の素数7を先頭に542個の素数を足した997651です。

Project Euler 92 / 桁の2乗による連鎖

各桁の2乗を足しあわせて新たな数を作ることを, 同じ数があらわれるまで繰り返す。たとえば次のような列を作る。

  • 44 → 32 → 13 → 10 → 1 → 1
  • 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

どちらも1か89で無限ループにおちいっている。驚くことに, どの数からはじめても最終的に1か89に到達する。

10,000,000より小さい数で89に到達する数はいくつあるか。

Problem 92 - Project Euler


「ある条件をみたすまで操作 f を繰り返す」は NestWhile[ ] でできます。また,途中経過は NestWhileList[ ] で見られます。44でためしてみましょう。


NestWhile[ ] の結果が89になるものを数えておしまい。

Project Euler 85 / 長方形の数え上げ

注意深く数えると横が3,縦が2の長方形の格子には18個の長方形が含まれている。

f:id:variee:20170416030959g:plain

ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない。一番近い解を持つような格子の面積を求めよ。

Problem 85 - Project Euler


いろいろ考えた結果,問題27の類題(記事の最後にリンク貼っておきます)だときづきました。

  • 問題27:ある量の最大値を与える(a, b)の積を求める
  • 問題85:ある量の最小値を与える(m, n)の積を求める

解答をはじめます。縦 m,横 n(m≦n)の長方形の切り分け方は二項係数であらわせて,C[m,2]*C[n,2] 通りです。
m=n の場合を考えると m の最大値がわかり,m=2 の場合を考えると n の最大値がわかります。


あとは問題27とほぼ同じで,C[m,2]*C[n,2] と 2*10^6 の差でソートして最小値を与える組を取り出します。m, n の範囲をしぼりこむまでもなく0.2秒で終わりました。


variee.hatenadiary.com

Project Euler 37 / 切り詰め可能素数

3797は面白い性質を持っている。まずそれ自身が素数であり,左から右に桁を除いたときにすべて素数になっている (3797, 797, 97, 7)。同様に右から左に桁を除いたときもすべて素数である (3797, 379, 37, 3)。

右から切り詰めても左から切り詰めても素数になる素数は11個しかない。その総和を求めよ。

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない。

Problem 37 - Project Euler


切り詰めた後の数はもとの数 n を 10^k で割ったときの商と余りです。
Quotient[n,10^k], Mod[n,10^k] で処理できます。
k の範囲は n の桁数 IntegerLength[n] を使って求めました。