2015-05-13

Problem 058: Spiral primes

Description:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

``````37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 05 04 03 12 29
40 19 06 01 02 11 28
41 20 07 08 09 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49``````

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of `8/13 = 62%`.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below `10%`?

Solution:
v####
v##
v#
v###     >             >             >      >\$0v
>             >              \$1v
>::2\`#^_:2-!#^_:2%!#^_:9\`#^_:3%!#^_:5%!#^_1 :v
2>^<v\                      p21:+1g21:_v#-3 <p2 1<
1  p>:11p1-0\>:2% !#v_v    v ++!!+1-g< #    ^ < >v
3  3         ^\+1\/2< \    >3-#v_\$\$  1>12g\  !|>|
p 31 vp01p03p04 g11p12<        >:*11v1 >\$1   #\$^
1 p+ >120pv        v%g04*<v-1\    %g<^ \!!-1:<\$0
2 32 vg030<  v-1\  < >10g^   >\:::*11  g%1-!\^>^
3 3g     >\$1\> :#v_ \$ 21g >:#^_\$1-!!  ^
p 03 >:!#^_\1+\2v\ ^_^#!%2/\g03p<  v    p33+1g33 <
> ^1 ^p02*2g02/ <>:*40g%20g2/:20^
^_^#%4g32+g31_v#`\*+55g33p32:+1g32<            <
@.+3*2/4-2g32\$<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

It's obvious that the bottleneck of this program is the primality test. The numbers become here too big to create a sieve and "normal" prime testing takes too long. So we use the Miller-Rabin primality test that I implemented a while ago (thank mathblog.dk).
The rest is just enumerating all the diagonals until `primes*10<all`

 Interpreter steps: 78 283 096 Execution time (BefunExec): 12s (6.42 MHz) Program size: 50 x 17 (fully conform befunge-93) Solution: 26241 Solved at: 2015-05-13

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript