Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
$2$の平方根は無限連分数として書くことができる.
\sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+・・・}}}}
無限連分数である $\sqrt{2} = [1;(2)]$ と書くことができるが, $(2)$ は$2$が無限に繰り返されることを示す. 同様に, $\sqrt{23} = [4;(1,3,1,8)]$.
平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.$\sqrt{2}$の近似分数について考えよう.
1+\frac{1}{2}=\frac{3}{2} \\
1+\frac{1}{2+\frac{1}{2}}=\frac{7}{5} \\
1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}=\frac{17}{12} \\
1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}}=\frac{41}{29}
従って, $\sqrt{2}$の近似分数からなる数列の最初の10項は：
$1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{3363}{2378}, ...$
もっとも驚くべきことに, 数学的に重要な定数,
$e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].$
$e$ の近似分数からなる数列の最初の$10$項は：
$2, 3, \frac{8}{3}, \frac{11}{4}, \frac{19}{7}, \frac{87}{32}, \frac{106}{39}, \frac{193}{71}, \frac{1264}{465}, \frac{1457}{536}, ...$
$10$項目の近似分数の分子の桁を合計すると$1+4+5+7=17$である.
$e$ についての連分数である近似分数の$100$項目の分子の桁の合計を求めよ.
アプローチ
$[2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]$を$\{b_n\}$とおき、
$b_0=2$、$b_1=1$、$b_2=2$、$b_3=1$、$b_4=1$、$b_5=4$...とする。
$e$の近似分数表記を数列$\{a_n\}$で表記する。
a_1=b_0+\frac{1}{b_1}=2+\frac{1}{1}=\frac{3}{1} \\
a_2=b_0+\frac{1}{b_1+\frac{1}{b_2}}=b_0+\frac{b_2}{b_1b_2+1}=2+\frac{2}{3}=\frac{8}{3} \\
a_3=b_0+\frac{1}{b_1+\frac{1}{b_2+\frac{1}{b_3}}}=b_0+\frac{b_2b_3+1}{b_3(b_1b_2+1)+b_1}=2+\frac{3}{4}=2+\frac{3}{4}=\frac{11}{4} \\
a_4=b_0+\frac{1}{b_1+\frac{1}{b_2+\frac{1}{b_3+\frac{1}{b_4}}}}=b_0+\frac{b_4(b_2b_3+1)+b_2}{b_4(b_3(b_1b_2+1)+b_1)+b_1b_2+1}=2+\frac{5}{7}=\frac{19}{7} \\
a_5=b_0+\frac{1}{b_1+\frac{1}{b_2+\frac{1}{b_3+\frac{1}{b_4+\frac{1}{b_5}}}}}=b_0+\frac{b_5(b_4(b_2b_3+1)+b_2)+b_2b_3+1}{b_5(b_4(b_3(b_1b_2+1)+b_1)+b_1b_2+1)+b_3(b_1b_2+1)+b_1+1}=2+\frac{23}{32}=\frac{87}{32} \\
・・・ \\
以上より$3<=n$に対して、
a_n=b_0+\frac{b_n*(a_{n-1}-b_0の分子)+(a_{n-2}-b_0の分子)}{b_n*(a_{n-1}-b_0の分母)+(a_{n-2}-b_0の分母)}
であることが分かる。
上記を$a_1$、$a_2$にも適応できるように下記を定義する。
a_0=b_0+\frac{0}{1} \\
a_{-1}=b_0+\frac{1}{0}
この法則に従い、$a_{99}$を求めればよい。
解答
time seq 99 |
awk 'a=($1+1)%3==0{print $1,2*($1+1)/3} !a{print $1,"1"}' |
awk -M 'BEGIN{s[-1]=1;b[-1]=0;s[0]=0;b[0]=1}{s[$1]=$2*s[$1-1]+s[$1-2];b[$1]=$2*b[$1-1]+b[$1-2];print $1,s[$1]+2*b[$1],b[$1]}' |
awk '$1==99{print $2}' |
awk -v FS= '{for(i=1;i<=NF;i++){s+=$i};print s}'
272
real 0m0.125s
user 0m0.015s
sys 0m0.229s
この問題はアプローチにかなり時間がかかりましたが、なんとか自力で解けました！
よかったです。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/065.html