ジョセフの日記

Haskellのこととか日常のこととか

ベクレミシェフの虫 part2

前回は定義そのままを計算してただけなので、今回は少しだけ再帰を減らすような計算を入れてやりました。
プログラムなどは続きを読むからどうぞ


入れてやる計算は次の3つです。

リストが[1]の場合

 Worm(step,[1])=Worm(2 \cdot step+3,[])

リストの末端が[0,1]の場合

 Worm(step,[A,0,1]) = Worm(2 \cdot step+4,[A])

リストの末端が[0,1,1]の場合

 Worm(step,[A,0,1,1]) = Worm(2^{(step+2)}(step+2)+4 \cdot {\displaystyle \sum_{i=1}^{step+2}}2^{i-1},[A])

ここで[A]は任意の非負整数リストです。
これを使うと、前回のプログラムでは計算できなかった初期リストも計算出来るようになります。

例えば初期リストが[1,1,1]のときは11059176924930500062559674741532466872315stepでリストを空に出来ます。
しかし[2,0]の場合は計算できず、非常に少なく見積もって196桁以上のstepがかかりそうです。

リストの末端が[0,1,\ldots,1](n個の1)の場合はstep数がn-2のときにリストの末端が[0,2]であることと対応しています。(おそらく)
なので、末端の[0,2]はstep数の分だけ強くした演算子を2とstep数に作用させる効果を持っていそうです。(おそらく)

今回のプログラムです。