Bash
ProjectEuler
数学

Project Euler Q61 【巡回図形数】

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

問題

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
三角数 $P_{3,n}=\frac{1}{2}n(n+1)$ $1, 3, 6, 10, 15, ...$
四角数 $P_{4,n}=n^2$ $1, 4, 9, 16, 25, ...$
五角数 $P_{5,n}=\frac{1}{2}n(3n-1)$ $1, 5, 12, 22, 35, ...$
六角数 $P_{6,n}=n(2n-1)$ $1, 6, 15, 28, 45, ...$
七角数 $P_{7,n}=\frac{1}{2}n(5n-3)$ $1, 7, 18, 34, 55, ...$
八角数 $P_{8,n}=n(3n-2)$ $1, 8, 21, 40, 65, ...$

$3$つの$4$桁の数の順番付きの集合 $(8128, 2882, 8281)$ は以下の面白い性質を持つ.

1.この集合は巡回的である. 最後の数も含めて, 各数の後半$2$桁は次の数の前半$2$桁と一致する
2.それぞれ多角数である: 三角数 $(P_{3,127}=8128)$, 四角数 $(P_{4,91}=8281)$, 五角数 $(P_{5,44}=2882)$ がそれぞれ別の数字で集合に含まれている
3.$4$桁の数の組で上の$2$つの性質をもつのはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる$6$つの巡回する$4$桁の数からなる唯一の順序集合の和を求めよ.

解答

time seq 999 |
awk '{print $1*($1+1)/2,$1^2,$1*(3*$1-1)/2,$1*(2*$1-1),$1*(5*$1-3)/2,$1*(3*$1-2)}' |
awk '{for(i=1;i<=NF;i++){if(length($i)==4){print i+2,$i,substr($i,1,2),substr($i,3,2)}}}' |
awk '{v[NR]=$0} END{for(k in v){for(j in v){print v[k],v[j]}}}' |
awk '$1!=$5' |
awk '$4==$7{print} $8==$3{print $5,$6,$7,$8,$1,$2,$3,$4}' |
sort -u |
awk '{v[NR]=$0} END{for(k in v){for(j in v){print v[k],v[j]}}}' |
awk '$1!=$9&&$1!=$13&&$5!=$9&&$5!=$13' |
awk '$8==$11{print} $16==$3{print $9,$10,$11,$12,$13,$14,$15,$16,$1,$2,$3,$4,$5,$6,$7,$8}' |
sort -u |
awk '{v[NR]=$0} END{for(k in v){for(j in v){print v[k],v[j]}}}' |
awk '$16==$19&&$26==$2&&$30==$6' |
awk '$17!=$1&&$17!=$5&&$17!=$9&&$17!=$13' |
awk '$21!=$1&&$21!=$5&&$21!=$9&&$21!=$13' |
sort |
head -1 |
awk '{print $2+$6+$10+$14+$18+$22}'
28684

real    0m23.533s
user    0m33.766s
sys     0m3.445s

これは何をやっているか記載するのが難しいのですが、
1.まず三角数~八角数をリストアップ
2.同じ角数にならないように総掛け
3.巡回になっているものを抽出(この段階で$2$連続になる)
4.上記の2.と3.をもう一度やる(この段階で$4$連続になる)
5.更にもう一度やる(この段階で$8$連続になる)
6.$6$連続部分までで三角数~八角数が表れている かつ 巡回になっているものを抽出

ということをやっています(日本語が下手ですみません)。

総掛けのロジックがいい案を思いつかなかったのでawkENDで二重ループするということになってしまいました。

答え合わせ

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