Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:
$\sqrt{N} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + ...}}}$
例えば, $\sqrt{23}$を考えよう.
$\sqrt{23} = 4 + \sqrt{23} - 4 = 4 + \frac{1}{\frac{1}{\sqrt{23} - 4}} = 4 + \frac{1}{1 + \frac{√23 - 3}{7}}$
となる.
この操作を続けていくと,
$\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + ...}}}}$
を得る.
操作を纏めると以下になる:
$a_0 = 4$, $\frac{1}{\sqrt{23}-4} = \frac{\sqrt{23}+4}{7} = 1 + \frac{\sqrt{23}-3}{7}$
$a_1 = 1$, $\frac{7}{\sqrt{23}-3} = \frac{7(\sqrt{23}+3)}{14} = 3 + \frac{\sqrt{23}-3}{2}$
$a_2 = 3$, $\frac{2}{\sqrt{23}-3} = \frac{2(\sqrt{23}+3)}{14} = 1 + \frac{\sqrt{23}-4}{7}$
$a_3 = 1$, $\frac{7}{\sqrt{23}-4} = \frac{7(\sqrt{23}+4)}{7} = 8 + \frac{\sqrt{23}-4}{1}$
$a_4 = 8$, $\frac{1}{\sqrt{23}-4} = \frac{\sqrt{23}+4}{7} = 1 + \frac{\sqrt{23}-3}{7}$
$a_5 = 1$, $\frac{7}{\sqrt{23}-3} = \frac{7(\sqrt{23}+3)}{14} = 3 + \frac{\sqrt{23}-3}{2}$
$a_6 = 3$, $\frac{2}{\sqrt{23}-3} = \frac{2(\sqrt{23}+3)}{14} = 1 + \frac{\sqrt{23}-4}{7}$
$a_7 = 1$, $\frac{7}{\sqrt{23}-4} = \frac{7(\sqrt{23}+4)}{7} = 8 + \frac{\sqrt{23}-4}{1}$
よって, この操作は繰り返しになることが分かる. 表記を簡潔にするために, $\sqrt{23} = [4;(1,3,1,8)]$と表す. $(1,3,1,8)$のブロックは無限に繰り返される項を表している.
最初の$10$個の無理数である平方根を連分数で表すと以下になる.
$\sqrt{2}=[1;(2)],$ period=$1$
$\sqrt{3}=[1;(1,2)]$, period=$2$
$\sqrt{5}=[2;(4)]$, period=$1$
$\sqrt{6}=[2;(2,4)]$, period=$2$
$\sqrt{7}=[2;(1,1,1,4)]$, period=$4$
$\sqrt{8}=[2;(1,4)]$, period=$2$
$\sqrt{10}=[3;(6)]$, period=$1$
$\sqrt{11}=[3;(3,6)]$, period=$2$
$\sqrt{12}= [3;(2,6)]$, period=$2$
$\sqrt{13}=[3;(1,1,1,1,6)]$, period=$5$
$N ≤ 13$で奇数の周期をもつ平方根は丁度$4$つある.
$N ≤ 10000$ について奇数の周期をもつ平方根が何個あるか答えよ.
アプローチ
頑張ってはみたが自力では解けそうにないので下記サイト様を参考にアプローチを組み立てる。
漫ろ草 SozoroGusa プロジェクトオイラー 問６４
$\frac{1}{\sqrt{23}-4} = 1 + \frac{\sqrt{23}-3}{7}$について、規則性を見出すことができなかった。
左辺$=\frac{c}{\sqrt{n}-b}・・・①$とおく。
右辺$=A+\frac{\sqrt{n}-B}{C}・・・②$とおき$A$、$B$、$C$を$b$、$c$、$n$であらわすことを考える。
まずは分母を有理数にする。
\frac{c}{\sqrt{n}-b}=\frac{c(\sqrt{n}+b)}{n-b^2}・・・③
次に右辺の分母を決める。
C=\frac{n-b^2}{c}⇔c=\frac{n-b^2}{C}・・・④
③に④を代入すると右辺$=\frac{\sqrt{n}+b}{C}・・・⑤$となる。
$t=int(\sqrt{n})$とおくと
\frac{\sqrt{n}+b}{C}=\frac{b+t}{C}+\frac{\sqrt{n}-t}{C}・・・⑥
であるので、
A=int(\frac{b+t}{C})・・・⑦
となる。$u=(b+t)\%C$とすると、
\begin{align}
\frac{\sqrt{n}+b}{C}&=\frac{b+t}{C}+\frac{\sqrt{n}-t}{C} \\
&=\frac{CA+u}{C}+\frac{\sqrt{n}-t}{C} \\
&=A+\frac{u}{C}+\frac{\sqrt{n}-t}{C} \\
&=A+\frac{\sqrt{n}-t+u}{C} \\
&=A+\frac{\sqrt{n}-(t-u)}{C}・・・⑧
\end{align}
以上より$A$、$B$、$C$をあらわすと、
A=int(\frac{b+t}{C})=int(\frac{b+int(\sqrt{n})}{C}) \\
B=t-u=int(\sqrt{n})-(b+int(\sqrt{n}))\%C \\
C=\frac{n-b^2}{c}
となる。これを再帰的に求めていけばよい。
なお再帰の終了判断は$A$、$B$、$C$の組み合わせが過去に出てきたかどうかである。
解答
time seq 10000 |
awk '{print $1,int(sqrt($1))}' |
awk '$2!=sqrt($1)' |
awk '{a=$2;b=a;c=1;for(i=1;i<=999;i++){if(n[$1,a,b,c]!=1){print $1,a;n[$1,a,b,c]=1;c=($1-b^2)/c;a=int((b+$2)/c);b=$2-((b+$2)%c)}else{break}}}' |
awk '{if(k!=$1){printf "\n"$0" "}else{printf $2" "};k=$1}' |
awk '(NF-2)%2!=0' |
wc -l
1322
real 0m1.079s
user 0m1.557s
sys 0m0.037s
この問題、やっとできました！
処理の大部分を$3$個目のawkでおこなっている。
後は整形だったり必要な値を計算したりなどなど。。
答え合わせ
こちらのサイト様と一致していればOKとした。
漫ろ草 SozoroGusa プロジェクトオイラー 問６４