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で