1 ! Copyright (c) 2009 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: fry kernel math math.primes math.ranges project-euler.common sequences ;
6 ! http://projecteuler.net/index.php?section=problems&id=58
11 ! Starting with 1 and solveling anticlockwise in the following way, a square
12 ! solve with side length 7 is formed.
14 ! 37 36 35 34 33 32 31
15 ! 38 17 16 15 14 13 30
19 ! 42 21 22 23 24 25 26
20 ! 43 44 45 46 47 48 49
22 ! It is interesting to note that the odd squares lie along the bottom right
23 ! diagonal, but what is more interesting is that 8 out of the 13 numbers lying
24 ! along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
26 ! If one complete new layer is wrapped around the solve above, a square solve
27 ! with side length 9 will be formed. If this process is continued, what is the
28 ! side length of the square solve for which the ratio of primes along both
29 ! diagonals first falls below 10%?
37 CONSTANT: PERCENT_PRIME 0.1
39 ! The corners of a square of side length n are:
43 ! (n-2)² + 4(n-1) = odd squares, no need to calculate
45 : prime-corners ( n -- m )
46 3 [1..b] swap '[ _ [ 1 - * ] keep 2 - sq + prime? ] count ;
48 : total-corners ( n -- m )
51 : ratio-below? ( count length -- ? )
52 total-corners 1 + / PERCENT_PRIME < ;
54 : next-layer ( count length -- count' length' )
55 2 + [ prime-corners + ] keep ;
57 : solve ( count length -- length )
58 2dup ratio-below? [ nip ] [ next-layer solve ] if ;
62 : euler058 ( -- answer )
65 ! [ euler058 ] 10 ave-time
66 ! 12974 ms ave run time - 284.46 SD (10 trials)