Bash
ProjectEuler
数学

Project Euler Q69 【トーティエント関数の最大値】

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

オイラーのトーティエント関数, $φ(n)$ [時々ファイ関数とも呼ばれる]は, $n$ と互いに素な $n$ 未満の数の数を定める. たとえば, $1, 2, 4, 5, 7,$ そして$8$はみな$9$未満で$9$と互いに素であり, $φ(9)=6.$

$n$ 互いに素な数 $φ(n)$ $n/φ(n)$
$2$ $1$ $1$ $2$
$3$ $1,2$ $2$ $1.5$
$4$ $1,3$ $2$ $2$
$5$ $1,2,3,4$ $4$ $1.25$
$6$ $1,5$ $2$ $3$
$7$ $1,2,3,4,5,6$ $6$ $1.1666...$
$8$ $1,3,5,7$ $4$ $2$
$9$ $1,2,4,5,7,8$ $6$ $1.5$
$10$ $1,3,7,9$ $4$ $2.5$

$n ≤ 10$ では $n/φ(n)$ の最大値は $n=6$ であることがわかる.

$n ≤ 1,000,000$で $n/φ(n)$ が最大となる値を見つけよ.

アプローチ

全て計算しようとするとものすごい時間がかかる。
どうにかして計算する量や対象を減らす必要がある。

$n≤1000$や$n≤10000$で実際にやってみると、求めるべき$n$は
「素因数分解したときにより多くの因数を持つ」ことが予想される。
※あくまで予想であり、特に根拠はない。

よって、まず素因数分解をおこない、因数の数が最大である値にだけ互いに素である値の数をカウントする。

$n≤10$のとき、$n=6$ 因数の種類:$2(2,3)$
$n≤100$のとき、$n=30$ or $60$ or $90$ 因数の種類:$3(2,3,5)$
$n≤1000$のとき、$n=210$ or $420$ or $630$ or $840$ 因数の種類:$4(2,3,5,7)$
・・・

解答

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 '{print $1,NF-1}' |
sort -k2,2nr |
awk 'NR==1{max=$2} $2==max{print}' |
awk '{for(i=1;i<$1;i++){print $1,i}}' |
awk '{a=$1;b=$2;r=a%b;while(r!=0){a=b;b=r;r=a%b};if(b==1){c[$1]++};print $2,c[$1],$1}' |
sort -k3,3n -k1,1nr |
uniq -f2 |
awk '{print $3,$3/$2}' |
sort -k2,2n -k1,1nr |
tail -1 |
awk '$0=$1'
510510

real    1m44.113s
user    2m11.793s
sys     0m1.152s

解き終わって調べてみると、素数をかけたものが答えになるようす。
それをふまえると、

time seq 20 |
factor |
awk 'NF==2{print $2}' |
head -7 |
awk 'BEGIN{a=1} {a*=$1} END{print a}'
510510

real    0m0.006s
user    0m0.001s
sys     0m0.009s

答え合わせ

こちらのサイト様と一致していればOKとした。
Project Euler 69 _ nとφ(n)の比 - PEをMathematicaで

参考にさせて頂いたサイト様

Project Euler 69 - maple0705のブログ