# 1138be746556

Problem 58

author | Steve Losh <steve@stevelosh.com> |
---|---|

date | Thu, 02 Mar 2017 18:04:08 +0000 |

parents | 6936c3316864 |

children | ead9bd0ff20e |

branches/tags | (none) |

files | src/euler.lisp |

## Changes

--- a/src/euler.lisp Thu Mar 02 16:50:43 2017 +0000 +++ b/src/euler.lisp Thu Mar 02 18:04:08 2017 +0000 @@ -151,34 +151,24 @@ (finding i :such-that (= 1 (mod v modulus))))) -(defun number-spiral (size) - ;; See problem 28 - (assert (oddp size) (size)) - (flet ((turn (dx dy) - (cond - ((and (= dx 1) (= dy 0)) (values 0 1)) - ((and (= dx -1) (= dy 0)) (values 0 -1)) - ((and (= dx 0) (= dy 1)) (values -1 0)) - ((and (= dx 0) (= dy -1)) (values 1 0))))) - (iterate - (with array = (make-array (list size size))) - (with i = 1) - (with x = (floor (/ size 2))) - (with y = (floor (/ size 2))) - (with dx = 1) - (with dy = 0) - (initially (setf (aref array y x) i)) - (for counter :from 1 :by 1/2) - (for run-length = (truncate counter)) - (iterate (repeat run-length) - (incf i) - (incf x dx) - (incf y dy) - (if (and (in-range-p 0 x size) - (in-range-p 0 y size)) - (setf (aref array y x) i) - (return-from number-spiral array))) - (setf (values dx dy) (turn dx dy))))) +(defun number-spiral-corners (size) + "Return a list of the corner values of a 'number spiral' of size `size`. + + `size` must be odd. The order of the corners in the resulting list is + unspecified. + + Note that the \"spiral\" of size one has just a single \"corner\": `1`. + + " + (assert (oddp size)) + (if (= 1 size) + (list 1) + (let ((leg (1- size)) + (final (square size))) + (list (- final (* 0 leg)) + (- final (* 1 leg)) + (- final (* 2 leg)) + (- final (* 3 leg)))))) (defun truncate-number-left (n amount &optional (radix 10)) @@ -1000,16 +990,8 @@ ;; ;; What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral ;; formed in the same way? - (let* ((size 1001) - (spiral (number-spiral size))) - (+ (iterate (for x :from 0 :below size) ; \ - (for y :from 0 :below size) - (summing (aref spiral y x))) - (iterate (for x :from (1- size) :downto 0) ; / - (for y :from 0 :below size) - (summing (aref spiral y x))) - ;; don't double-count the center... - (- (aref spiral (truncate size 2) (truncate size 2)))))) + (iterate (for size :from 1 :to 1001 :by 2) + (summing (apply #'+ (number-spiral-corners size))))) (defun problem-29 () ;; Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5: @@ -1730,6 +1712,40 @@ (counting (> (digits-length (numerator expansion)) (digits-length (denominator expansion)))))) +(defun problem-58 () + ;; 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 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 + ;; + ;; 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%? + (labels ((score (value) + (if (primep value) 1 0)) + (primes-in-layer (size) + (sum (number-spiral-corners size) :key #'score))) + (iterate + (for size :from 3 :by 2) + (for count :from 5 :by 4) + (sum (primes-in-layer size) :into primes) + (for ratio = (/ primes count)) + (finding size :such-that (< ratio 1/10))))) + + + + (defun problem-74 () ;; The number 145 is well known for the property that the sum of the factorial @@ -1857,9 +1873,10 @@ (test p55 (is (= 249 (problem-55)))) (test p56 (is (= 972 (problem-56)))) (test p57 (is (= 153 (problem-57)))) +(test p58 (is (= 26241 (problem-58)))) (test p74 (is (= 402 (problem-74)))) (test p145 (is (= 608720 (problem-145)))) -;; (run! :euler) +(run! :euler)