読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 77 / 素数の和

10は素数の和として5通りに表すことができる。

  • 7 + 3
  • 5 + 5
  • 5 + 3 + 2
  • 3 + 3 + 2 + 2
  • 2 + 2 + 2 + 2 + 2

素数の和としての表し方が5000通り以上になる最初の数を求めよ。

Problem 77 - Project Euler


n の表し方を f(n) 通りとおいて,はじめは

 f(n)=f(n-2)+f(n-3)+\cdots+f(n-p_i)+\cdots

のような漸化式を考えました。p_i は素数です。

ただ,この方法だと 2+(2+3+3) と 3 +(2+2+3) のようなダブルカウントが生じてしまうので,素数の個数や最大値で場合分けして f(n, k) のような2変数の漸化式を使うことになるでしょう。

この方向でも考えたのですが,Mathematica には整数の分割用のコマンド IntegerPartitions がありました。

使う素数は Prime[Range[PrimePi[n]]] で「n以下の素数」を指定できます。

以上をまとめて出来上がり。


ついでに f(n) の具体的な値を見てみましょう。グラフも描いてみました。f(n) が増加関数なのは直感的にはあきらかですが,随分と急な変化をするものだなと思います。

f:id:variee:20170325131225p:plain