Bash
ProjectEuler
数学

Project Euler Q70 【トーティエント関数の置換】

More than 1 year has passed since last update.

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で