Bash
ProjectEuler
数学

Project Euler Q51 【素数の桁置換】

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

$*3$の第$1$桁を置き換えることで, $13, 23, 43, 53, 73, 83$という$6$つの素数が得られる.

$56**3$の第$3$桁と第$4$桁を同じ数で置き換えることを考えよう. この$5$桁の数は$7$つの素数をもつ最初の例である: $56003, 56113, 56333, 56443, 56663, 56773, 56993.$ よって, この族の最初の数である$56003$は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで$8$つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

アプローチ(参考サイトを閲覧した後に記載している)

1.置換する桁は何桁でもいい(問題文から読み取れなかった)
2.置換する桁数は$3$の倍数(根拠がよく分からない)
3.$1$の位は置換してはならない(これは分かる)
4.$8$個置換するのだから$0,1,2$のいずれかで置換可能
5.最小の素数には$0,1,2$が$2$つ以上含まれる

解答

$ time seq 100000 999999 |
factor |
awk 'NF==2{print $2}' |
awk -v FS= '{delete s;printf $0" ";for(i=1;i<=NF;i++){s[$i]+=1};print length(s),s[0]"_",s[1]"_",s[2]"_"}' |
awk '{print $1,$3*1,$4*1,$5*1}' |
awk '{for(i=2;i<=NF;i++){if($i<2){continue};printf $1" ";for(j=0;j<=9;j++){printf gensub(i-2,j,"g",$1)" "};print ""}}' |
factor |
tr ' ' '_' |
xargs -n11 |
tr '_' ' ' |
awk '{for(i=1;i<=NF-1;i++){if(0<index($i,":")){if($i*1==$(i+1)){printf $(i+1)" "}}};print ""}' |
awk 'NF==9&&length==(6*9+9){print $1}'
121313

real    0m27.373s
user    0m11.550s
sys     0m19.835s

また問題文を正しく読み取れなかった。。
置換する桁数は何桁でもいいだなんて。。

全体的に超強引に解きました。
gensubは使わないと忘れる。
非破壊置換だからすごく便利!

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/051.html

参考にさせて頂いたサイト様

Project Euler 51 - 桃の天然水
Project Euler - Problem 51 1.1s (Ruby 1.9) ツムジのひとりごと
これは強力! AWKとパイプの新しい関係 ~ 時刻を取得する関数、Socket通信、双方向パイプ (1_2):CodeZine(コードジン)