Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
$n$と$d$を正の整数として, 分数 $\frac{n}{d}$ を考えよう. $n<d$ かつ $HCF(n,d)=1$ のとき, 真既約分数と呼ぶ.
$d ≤ 8$について既約分数を大きさ順に並べると, 以下を得る:
$\frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}$
$\frac{3}{7}$のすぐ左の分数は$\frac{2}{5}$である.
$d ≤ 1,000,000$について真既約分数を大きさ順に並べたとき, $\frac{3}{7}$のすぐ左の分数の分子を求めよ.
解答
time seq 5 1000000 |
awk '{for(i=int($1*3/7);($1*2/7)<=i;i--){a=$1;b=i;r=a%b;while(r!=0){a=b;b=r;r=a%b};if(b==1){print $1,i;next}}}' |
awk '{if(a[$2]!=1){printf("%d %d %1.10f\n",$1,$2,$2/$1);a[$2]=1}}' |
sort -k3,3n |
grep -B1 "^7 3 " |
awk '{print $2;exit}'
428570
real 0m5.700s
user 0m7.690s
sys 0m0.144s
最初は全件を対象にしていた為ものすごい時間がかかった。
最初のawkでforの範囲を限定したり、値を列挙しつつユークリッドの互除法をしたり、
分子が同じ数なら分母が小さい方がでかい数だよね、という考えを適用したりして
対象をどんどん少なくしていき、なんとか処理時間を短くすることに成功した。
このような数列をファレイ数列というらしい。
ファレイ数列 - Wikipedia
ファレイ数列の性質として、
$\frac{2}{5}$と$\frac{3}{7}$の間に$\frac{2+3}{5+7}=\frac{5}{12}$が存在する。
これを$d ≤ 1,000,000$の範囲で繰り返していけばよい。
この性質を利用すると、
time echo 2 5 |
awk '{a=$1;b=$2;while(b<=10^6){a+=3;b+=7};print a-3}'
428570
real 0m0.034s
user 0m0.034s
sys 0m0.001s
速攻で解けた。。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/071.html