Bash
ProjectEuler
数学

Project Euler Q73 【ある範囲内の分数の数え上げ】

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{1}{3}$と$\frac{1}{2}$の間には3つの分数が存在することが分かる.

では, $d ≤ 12,000$ について真既約分数をソートした集合では, $\frac{1}{3}$と$\frac{1}{2}$ の間に何個の分数があるか?


解答

time seq 2 12000 |

awk '{for(i=int($1/3);i<=$1/2;i++){print $1,i,i/$1}}' |
awk '1/3<$3&&$3<1/2' |
awk '{a=$1;b=$2;r=a%b;while(r!=0){a=b;b=r;r=a%b};if(b==1){print}}' |
wc -l
7295372

real 0m23.675s
user 0m44.568s
sys 0m0.486s

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

ファレイ数列 - Wikipedia

この問題もファレイ数列の性質を使うとスマートに解けるのかもしれないが、思いつかなった。


答え合わせ

こちらのサイト様と一致していればOKとした。

http://kingyojima.net/pje/073.html