Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
オイラーのトーティエント関数 $φ(n)$ (ファイ関数とも呼ばれる) とは, $n$ 未満の正の整数で $n$ と互いに素なものの個数を表す. 例えば, $1, 2, 4, 5, 7, 8$ は$9$未満で$9$と互いに素であるので, $φ(9) = 6$ となる.
$1$ は全ての正の整数と互いに素であるとみなされる. よって $φ(1) = 1$ である.
面白いことに, $φ(87109)=79180$ であり, $87109$は$79180$を置換したものとなっている.
$1 < n < 10^7$ で $φ(n)$ が $n$ を置換したものになっているもののうち, $n/φ(n)$ が最小となる $n$ を求めよ.
アプローチ
$φ(n)$の導出
$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ $p_1<p_2<...<p_k$
と素因数分解できるとき、$φ(n)$は下記式で表せる。
φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})
以上、引用元：Project Euler 69 - maple0705のブログ
解答
time seq 2 10000000 |
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 'length($1)==length($2)' |
awk '{split($1,a,"");split($2,b,"");n=asort(a);m=asort(b);printf $0" ";for(i=1;i<=n;i++){printf a[i]};printf " ";for(i=1;i<=m;i++){printf b[i]};print ""}' |
awk '$3==$4{printf("%d %1.10f\n",$1,$1/$2)}' |
sort -k2,2n |
head -1 |
awk '$0=$1'
8319823
real 1m19.407s
user 2m27.063s
sys 0m1.186s
数学的なアプローチがよく分からなかったので全件計算した。
$n/φ(n)$を計算する処理で四捨五入の関係がある為、有効数字を増やして計算しないと同じ値になってしまい、結果取得する$n$が変わってしまう現象が起きた。
計算に時間がかかっているが、対象が多い為よしとする。
答え合わせ
こちらのサイト様と一致していればOKとした。
Project Euler 70 _ ファイ関数の置換 - PEをMathematicaで