Bash
ProjectEuler
数学

Project Euler Q58 【螺旋素数】

More than 1 year has passed since last update.

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