Bash
ProjectEuler
数学

Project Euler Q72 【分数の数え上げ】

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}$

この集合は$21$個の要素をもつことが分かる.

$d ≤ 1,000,000$について, 真既約分数の集合は何個の要素を持つか?


アプローチ

要するに、

$φ(2)+...+φ(1,000,000)$を求めればよい。


解答

time seq 2 1000000 |

factor |
awk '{delete a;printf $1*1" ";for(i=2;i<=NF;i++){a[$i]=1};for(k in a){printf k" "};print ""}' |
awk '{a=$1;for(i=2;i<=NF;i++){a*=(1-1/$i)};print $1,a}' |
awk '{a+=$2} END{print a}'
303963552391

real 0m3.526s
user 0m6.590s
sys 0m0.075s

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

ファレイ数列 - Wikipedia

自力で気づけたからよかったが、ファレイ数列の長さを求めるときにトーティエント関数が登場するようだ。


答え合わせ

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

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