Project Euler の 220 番目を眺めていて、帰ってこれなくなった。

数学

Project Euler の 220 番目を眺めていて、母関数の国から数列の国に帰ってこれなくなった。


Problem 220 - Project Euler 問題のページ
Problem 220 - PukiWiki 日本語訳

とりあえず普通に

とりあえず普通に解こうとすると、

  1. 置換手続きを書いて、それに "Fa" という文字列を与えて、
  2. 帰ってきた文字列をまた置換手続きに与えて･･････を 50 回繰り返す
  3. その文字列にしたがって、ロボットを動かす。（仮想的に。座標と、向きだけを逐次変更していく。）


ということになると思うのだけど、実際に置換手続きを書いて動かしてみると処理が帰ってこない。


なので、プログラムをちょっと変更して、文字列がどんな風に変化していくのかを表示させてみた：

D0 = Fa
D1 = FaRbFR
D2 = FaRbFRRLFaLbFR
D3 = FaRbFRRLFaLbFRRLFaRbFRLLFaLbFR
D4 = FaRbFRRLFaLbFRRLFaRbFRLLFaLbFRRLFaRbFRRLFaLbFRLLFaRbFRLLFaLbFR


わりと急速に大きな文字列になるっぽい。


D0 から D4 までの文字列の長さはそれぞれ、2, 6, 14, 30, 62 だ。 Dn が Dn+1 になるとき、文字列の長さは「1 足して 2 倍」になってる。あるいは、「2 倍して 2 足す」になってる。

Dn の長さを Fn とおく,
F0 = 2
Fn = 2 * (Fn-1 + 1) = 2Fn-1 + 2

*1


F50 はいったいどれくらいの大きさなんだろう。


F50 を知るために、この漸化式を、n について閉じた式で表したい。そこで、次の手順を踏む：

  1. 数学ガール (数学ガールシリーズ 1) の『第 4 章 フィボナッチ数列と母関数』をじっくり読む。
  2. 椅子を蹴っ飛ばされたテトラちゃんがどうなるのか、というその後の展開のことはいったん忘れる。

出発

それでは、母関数の国に出発します。

F0 = 2
Fn = 2Fn-1 + 2  (n ≧ 1)


この数列に対応する母関数を F(x) と呼ぶことにする。

F(x) = F0x0 + F1x1 + F2x2 + F3x3 + ･･･


結城さんの本の中では、この母関数に x0 や x1 や x2 を掛けていた。真似してみる：

式A:  F(x)・x2 = F0x2 + F1x3 + F2x4 + F3x5 + ･･･
式B:  F(x)・x1 = F0x1 + F1x2 + F2x3 + F3x4 + ･･･
式C:  F(x)・x0 = F0x0 + F1x1 + F2x2 + F3x3 + ･･･


ここで、「ミルカさんは、なんのために x1 や x2 を掛けたんだっけ？」と考えてみると、それは、フィボナッチ数列の漸化式を使って、母関数の「ある場所から後ろ」をバッサリ消したかったから。


そのためには、x の次数を合わせて、式同士を足したり引いたりする必要があったからだ。


私が持ってる漸化式はこれだ。

Fn = 2 * (Fn-1 + 1) = 2Fn-1 + 2


等式の、真ん中の部分を省いて、もう一度書くと：

Fn = 2Fn-1 +2


右辺の全ての項を、左辺に移項して、

Fn - 2Fn-1 -2 = 0


これを眺めながら、さっき作った式A、式B、 式C を x の次数にあわせてインデントしつつ眺めてみる。

式A:  F(x)・x2 =             F0x2 + F1x3 + F2x4 + F3x5 + ･･･
式B:  F(x)・x1 =       F0x1 + F1x2 + F2x3 + F3x4 + ･･･
式C:  F(x)・x0 = F0x0 + F1x1 + F2x2 + F3x3 + ･･･


式A は、なんだか今回は必要なさそう。


そうか、式B は、惜しいところまで行っていた。式Bの両辺を2倍して、式2B とする。：

式 C:  F(x)・x0  = F0x0 + F1x1 + F2x2 + F3x3 + ･･･
式2B:  F(x)・2x1 =      2F0x1 + 2F1x2 + 2F2x3 + 2F3x4 + ･･･


むぅ･･････。こんな式が欲しい：

式 ?:  G(x) = 2x0 + 2x1 + 2x2 + 2x3 + ･･･


わけのわからない式を導入するより、式C から式2B を引いてみる。まず左辺：

F(x)・x0 - F(x)・2x1
= F(x) - F(x)2x
= F(x)・(1 - 2x)


右辺：

F0x0 + (F1 - 2F0)・x1 + (F2 - 2F1)・x2 + (F3 - 2F2)・x3 + ･･･
= F0x0 + 2x1 + 2x3 + 2x4 + ･･･


右辺と左辺は等しかったので、もう一度、等号で結んで書き直すと：

F(x)・(1 - 2x) = F0x0 + 2x1 + 2x3 + 2x4 + ･･･


F0 は、D0 の長さだった。2 だ。 そんで、x0 は、1 のことだ：

F(x)・(1 - 2x) = 2・1 + 2x1 + 2x3 + 2x4 + ･･･

F(x) = (2 + 2x + 2x3 + 2x4 + ･･･) / (1 - 2x)

どうすればいいんだろう･･････。ミルカさん来てくれたらなぁ。

参考

数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)

まだ、「母関数」ってものについて、ちゃんとわかってないので、またじっくり読みます。

*1:ここでは Project Euler の問題文の通りに D0 を二文字 "Fa" として扱うけど、D0 を長さゼロの文字列 "" として扱ったほうがいいのかな。