Bash
ProjectEuler
数学

Project Euler Q57 【平方根の近似分数】

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

$2$の平方根は無限に続く連分数で表すことができる.
$\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ... }}} = 1.414213...$

最初の$4$回の繰り返しを展開すると以下が得られる.

$1 + \frac{1}{2} = \frac{3}{2} = 1.5$
$1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5} = 1.4$
$1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12} = 1.41666...$
$1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} = \frac{41}{29} = 1.41379...$

次の$3$つの項は$\frac{99}{70}, \frac{239}{169}, \frac{577}{408}$である. 第$8$項は$\frac{1393}{985}$である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の$1000$項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつあるか?

アプローチ

$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}$

を整理すると、

$a_1=1 + \frac{1}{2} =\frac{1+1}{1+1}+\frac{1}{1+1}= \frac{3}{2}$
$a_2=1 + \frac{1}{2 + \frac{1}{2}} =1+\frac{1}{1+\frac{3}{2}}=\frac{2+3}{2+3}+\frac{2}{2+3}= \frac{7}{5}$
$a_3=1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} =1+\frac{1}{1+\frac{7}{5}}=\frac{5+7}{5+7}+\frac{5}{5+7}= \frac{17}{12}$
$a_4=1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} =1+\frac{1}{1+\frac{17}{12}}=\frac{12+17}{12+17}+\frac{12}{12+17}= \frac{41}{29}$

上記より$2<=n$に対して、

a_n=\frac{2*a_{n-1}の分母+a_{n-1}の分子}{a_{n-1}の分母+a_{n-1}の分子}

となる。

$a_0=\frac{1}{1}$と定義すれば上記漸化式は$n=1$のときにも成り立つ。

解答

time seq 1000 |
awk -M 'BEGIN{s=b=1} {c=b+s;t=2*b+s;print c,t;b=c;s=t}' |
awk 'length($1)<length($2)' |
wc -l
153

real    0m0.515s
user    0m0.031s
sys     0m0.215s

アプローチができるかどうかがポイントですね。
また最初のawkで変数ctを登場させてますが、bsをそのまま計算してしまうと先に計算した方が反映されてしまうのでうまく計算できません。
その為、退避する必要があります。

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/057.html