https://goo.gl/L9mprh Problem 70 - PukiWiki
seq 2000 5000 | factor | awk 'NF==2{a[++n]=$2}END{for(i=1;i<=n;i++)for(j=i;j<=n;j++)print a[i],a[j],a[i]*a[j]}' | awk '$3<10000000{print $3,($1-1)*($2-1)}' | awk 'length($1)==length($2){split("",a);split("",b);for(i=1;i<=length($1);i++){a[substr($1,i,1)]++;b[substr($2,i,1)]++}for(v in a)if(a[v]!=b[v])next;print $1";"$2";"$1"/"$2}' | bc -l | awk 'NR%3{printf $1" "}NR%3==0{print}' | awk -v a=2 '$3<a{n=$1;p=$2;a=$3}END{print "n="n,"phy(n)="p,"Min(n/phy(n))="a}'
n=8319823 phy(n)=8313928 Min(n/phy(n))=1.00070905112481128054 real 0m0.229s user 0m0.290s sys 0m0.050s
計算量を減らすための戦略
https://goo.gl/UVsISK オイラーのφ関数 - Wikipedia
https://goo.gl/zRnkqW Project Euler 70: φ(n) is a permutation of n. | MathBlog
置換数という条件を一旦忘れると、10^7 に最も近い素数であれば、n/phy(n)が最小になる
なぜなら素数の場合、phy(n)=n-1 だから
置換数という条件を考えると、
単一の素数では条件を満たさないことは明らか。n と n-1 が置換数になるわけがない。
nが複数の素数の積だった場合、n=p*q*r... とおくと、n/phy(n)=p/(p-1) * q/(q-1) * r/(r-1) ... となる
ここで x/(x-1) > 1 だから、素数の数は少ないほどよいので、2つの素数の積を考える
n/phy(n) = p/p(-1) * q(q-1) なので、素数は sqrt(10^7) に近いものほど大きくなる
ここで sqrt(10^7) = sqrt(10) * 1000 = 3.16 * 1000
3.16 の前後の素数は 2,5 なので、2000..5000 の間の素数の積について、
n と phy(n) を求め、置換数であるもののうち、 最も n/phy(n) が小さいものを探す
# 素数を探す範囲
seq 2000 5000 |
# 素数だったら
factor | awk 'NF==2{
# 一旦、配列に格納
a[++n]=$2
}END{
# 素数を掛け合わせ、素数1,素数2,素数の積 を出力
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
print a[i],a[j],a[i]*a[j]
}' |
# 10^7 未満であったら、n,phy(n)を出力
awk '$3<10000000{print $3,($1-1)*($2-1)}' |
# 置換数の判定
awk 'length($1)==length($2){
# n, phy(n) それぞれについて、0-9 が何個使われているかを計算
# n : $1, a
# phy(n): $2, b
split("",a);
split("",b);
for(i=1;i<=length($1);i++){
a[substr($1,i,1)]++;
b[substr($2,i,1)]++
}
# 置換数ではなければ、処理をスキップ
for(v in a)
if(a[v]!=b[v])
next;
# 置換数であれば、n/phy(n) を bc で計算するための式を出力
# もし awk で計算してしまうと、小数点以下の桁丸めが生じ、正しく計算できない(ので間違った答えを得る)
print $1";"$2";"$1"/"$2
}' |
# bc で n, phy(n), n/phy(n) を逐次計算
bc -l |
# bc の出力結果を、3行毎に1行(1行は3列)に直す
awk '
NR%3 {printf $1" "}
NR%3==0{print}
' |
# 最小の n/phy(n) を求める
awk -v a=2 '$3<a{
n=$1;
p=$2;
a=$3
}END{
print "n="n,"phy(n)="p,"Min(n/phy(n))="a
}'