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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 340 / クレイジー関数

整数 a, b, c に対してクレイジー関数 F(n) を次のように定義する。

  • F(n) = n - c (n > b のとき)
  • F(n) = F(a + F(a + F(a + F(a + n)))) (n ≤ b のとき)

また, S(a, b, c) =Σ[n=0,b] F(n) と定義する。

たとえば a = 50, b = 2000, c = 40 ならば
F(0)=3240, F(2000)=2040, S(50, 2000, 40)=5204240
である。

S(21^7, 7^21, 12^7) の下9桁を求めよ。

Problem 340 - Project Euler

グラフを描いてみる

「本当に well-defined なんだろうか?」と感じる式だったので,ListPlot してグラフを描いてみました。

f:id:variee:20170511202559p:plain

f:id:variee:20170511202419p:plain

x<2000 では周期50です。各周期のはじめの値を調べると,公差は -30。一周期かけて 50(=a?) 増加した後は,80(=2c?) 減少して次の周期に移っています。

具体的な関数形を求める

a+n>b, n≦b のとき

 f(a+n)=n+a-c

この問題では a>c としてかまわないので,

 a+f(a+n)=n+a+(a-c)> n+a>b

この調子で内側から処理していくと

 f(n)=n+4a-4c\quad (b-a+1\leqq n\leqq b)

となります。これを平行移動して,

 f(n)=n+4(k+1)a-(3k+4)c

 \quad\quad (b-(k+1)a+1\leqq n\leqq b-ka)

各区間における f(n) の和は

 g(k)=\dfrac{1}{2} (50 + 50 k - ka) (4031 + 110 k - ka)

k の範囲は 0≦k≦ [b/a]=310115716 です。この範囲で g(k) の和を取りたいところですが,k= [b/a]=310115716 に対応する最初の区間のみ途中からはじまります。

0≦n≦1611673651 から,この区間での和は

 \dfrac{f(0)+f(1611673651)}{2}\cdot 1611673652

以上の和を取れば終わりです。ただ,a, b, c が非常に大きい数なので f, g を残したままでは計算できません。g(k) の和と最初の区間の和をあらかじめ a, b, c で表しておいて,最終的な計算だけ Mathematica にやってもらいました。このコードだけ見ると,何をやっているのか全然わからないですね。