問題(和訳)

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
 }'

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-03-24 (日) 07:44:02