Edited at

Project Euler Q71 【順序分数】

More than 1 year has passed since last update.

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

最初は全件を対象にしていた為ものすごい時間がかかった。

最初のawkforの範囲を限定したり、値を列挙しつつユークリッドの互除法をしたり、

分子が同じ数なら分母が小さい方がでかい数だよね、という考えを適用したりして

対象をどんどん少なくしていき、なんとか処理時間を短くすることに成功した。

このような数列をファレイ数列というらしい。

ファレイ数列 - 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