この記事は円周率チャレンジの最適解が53であることを示し、
私のように無駄に52以下の解を探して時間を溶かさないようにするための記事です。
なお、当記事は円周率チャレンジの解法のネタバレを含みます。自己責任で閲覧ください。
円周率チャレンジについて
概要
円周率チャレンジを数学的に述べると次のような問題です。
g_1(x) = x + 2 \\
g_2(x) = \sqrt{x}
とする。このとき
関数の列$f_1,\dots, f_n$ ただし$f_i \in { g_1, g_2}$であって
$$ \pi = f_1 \circ f_2 \circ \dots \circ f_n (0)$$
となるもののうち最も短いものを求めよ。
ランキングを見ると現状の最適解が53であることがわかります。
それでは52以下の解は存在するのでしょうか？
考察
今探している解の長さの上限を固定して$N$と置きます。具体的には$N = 53$
です。
このとき、最適解$f_1, \dots, f_n$に関する必要条件として以下のことが成り立ちます。
- $f_n = g_1$として良い。
- なぜなら$f_n = g_2$のときは$f_1, \dots, f_{n-1}$も解となり最適性に矛盾します。
- $i < n$のとき$f_i$の引数の値($f_{i+1} \circ \dots \circ f_n (0)$のこと)は$1$以上$2 (n - i)$以下である。
- これは数学的帰納法で示せます。
これらの性質を用いて解を$f_1$から順に枝狩り探索で探します。
解法
次のような疑似コードで示されるアルゴリズムは長さN以下の解を全探索します。
$\pi$からスタートするのがポイントです。
pi = 3.141592653589793
def dfs(f_1,...,f_k, v):
if f_1 ... f_k(v) == pi:
print f_1,...,f_k
else:
for f_{k+1} in [g_1, g_2]:
v1 = f_{k+1}^{-1}(v) # f_{k+1}の逆関数
if f_1 ... f_{k+1}(v1) == pi:
print f_1,...,f_{k+1}
elif 1 < v1 < 2(N - k - 1):
dfs(f_1,...,f_{k+1}, v1)
def main():
dfs([], pi)
このアルゴリズムをHaskellで実装してみるとちょうど長さ53の解が一つ見つかりました。
（ネタバレ防止のため解そのものはprintしていませんが、ネタバレしたくないひとは見ないことをおすすめします。）
実行結果
結論
円周率チャレンジの最適解は53です。52以下の解を探して時間を無駄にされませんように。
追記
とか書いていたら$N = 50$の解がランキングに載っていました。どういうことなの。。。