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