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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 101 / 最適多項式

数列のk個の項を与えられたときに,次の項を確実に求めることは不可能である。その数列にあう多項式が無限個存在するからである。

例として立方数の数列を考えよう。これは生成関数 u_n = n^3 で定義され,1,8,27,64,125,216,...となる。

この数列の最初の2項のみが与えられているとしよう。"Simple is best"の法則にのっとり,線形の関係があると仮定し,3つ目の項が15であると予想する (差分が7),もし最初の3項のみが与えられていた場合,同じ原則により二次の関係があると仮定して次の項を予測する。

数列の最初のk項を生成できる最適な多項式のn項を OP(k, n) で表すことにする。明らかに n ≤ k について OP(k, n) は正しい。最初の異なる項(First Incorrect Term, FIT)は OP(k, k+1) であろう。これを bad OP (BOP) と呼ぶことにする。

原則より,最初の項しか与えられていない場合には定数項とするのが理に適っているだろう。すなわち n ≥ 2, OP(1, n) = u_1

立方数の数列について以下のOPを得る。

OP(1, n) = 11, 1, 1, 1, ...
OP(2, n) = 7n−61, 8, 15, ...
OP(3, n) = 6n2−11n+61, 8, 27, 58, ...
OP(4, n) = n31, 8, 27, 64, 125, ...

明らかに k ≥ 4 のときにはBOPは存在しない。

BOPのFIT(上の例では赤で示されている)の和は 1+15+58 = 74 である。

以下の10次多項式からなる生成関数を考える。

u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^10

BOPのFITの総和を求めよ。

Problem 101 - Project Euler


多項式補間の問題ですね。Mathematica は InterpolatingPolynomial[ ] で簡単に補間多項式が作れるので,問題文に解法が書いてあるようなものです。例としてあげられている n^3 で試してみました。


これを u_n でやればおしまい。

問題文の「最初の異なる項は OP(k, k+1) であろう」「明らかに k≥4 のときにはBOPは存在しない」に一瞬「ん?」となりましたが,10次式の補間をするには11個のデータが必要なこと,元の式と補間式の差をとってその根の数を考えれば,k=1~10 について op[k, k+1] の和を求めればいいことは明らかです。