Spiral primes

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

Download

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