Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
$1$から始めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが$7$の渦巻きが形成される.
| 37 | 36 | 35 | 34 | 33 | 32 | 31 |
|---|---|---|---|---|---|---|
| 38 | 17 | 16 | 15 | 14 | 13 | 30 |
| 39 | 18 | 5 | 4 | 3 | 12 | 29 |
| 40 | 19 | 6 | 1 | 2 | 11 | 28 |
| 41 | 20 | 7 | 8 | 9 | 10 | 27 |
| 42 | 21 | 22 | 23 | 24 | 25 | 26 |
| 43 | 44 | 45 | 46 | 47 | 48 | 49 |
面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の$13$個の数字のうち, $8$個が素数である. ここで割合は$\frac{8}{13} ≈ 62\%$である.
渦巻きに新しい層を付け加えよう. すると辺の長さが$9$の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が$10$%未満に落ちる最初の辺の長さを求めよ.
アプローチ
$2～9$を$1$層目、$10～25$を$2$層目(以下同様)とする。
$1$から見て右上、右下、左上、左下方向にあらわれる数字をそれぞれ考える。
$m$を$1$以上の整数とし、いま$m$層目まで巻いているとする。
1.右上方向
あらわれる数字は$3,13,31,57,...$
階差数列は$10,18,26,...$
階差数列は初項$10$,公差$8$の等差数列であり、$k$を$1$以上の整数としたとき、一般項$b_k$は
$b_k=8k+2$
である。
よって右上方向に現れる数字の一般項$a_n$は、$n$が$2$以上の整数とすると
a_n=3+\sum_{k=1}^{n-1}(8k+2)=4n^2-2n+1
となる。
これは$n=1$のときにも成り立つ為、$n=m$としてよい。
つまり、$m$層目の右上の値は$4m^2-2m+1$である。
2.右下方向
上記と同様にして、$a_m=4m^2+4m+1$を得る。
3.左上方向
上記と同様にして、$a_m=4m^2+1$を得る。
4.左下方向
上記と同様にして、$a_m=4m^2+2m+1$を得る。
$m$層目での対角線上の値の数は$1+4m$個である。
$m$層目の辺の長さは$2m+1$である。
解答
time seq 99999 |
awk '{print 4*$1^2-2*$1+1,4*$1^2+4*$1+1,4*$1^2+1,4*$1^2+2*$1+1}' |
factor |
awk '{print NF==2}' |
paste -d" " - - - - |
awk '{for(i=1;i<=4;i++){s+=$i};print s/(1+4*NR)}' |
awk '$1<0.1{print 2*NR+1}' |
head -1
26241
real 0m0.249s
user 0m0.449s
sys 0m0.020s
factorで縦一列になってしまったのを$4$つずつに並べる方法がいい方法がなかった。
最近まではxargs -n4を使用していたが、これは(おそらく)echoをたくさん呼び出すので遅くなってしまう。
pasteでできることを最近知ったが、これが$10$個ずつとかになると面倒なので何かいい方法を探したい。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/058.html