# 6936c3316864

Problems 55 and 57

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

date | Thu, 02 Mar 2017 16:50:43 +0000 |

parents | 639c1d3616ce |

children | 1138be746556 |

branches/tags | (none) |

files | src/euler.lisp |

## Changes

--- a/src/euler.lisp Thu Mar 02 14:57:28 2017 +0000 +++ b/src/euler.lisp Thu Mar 02 16:50:43 2017 +0000 @@ -1,6 +1,16 @@ (in-package :euler) ;;;; Utils -------------------------------------------------------------------- +(defmacro-driver (FOR var ITERATING function INITIALLY value) + (let ((kwd (if generate 'generate 'for))) + (with-gensyms (f) + `(progn + (with ,f = ,function) + (,kwd ,var + :initially (funcall ,f ,value) + :then (funcall ,f ,var)))))) + + (defmacro-driver (FOR var IN-DIGITS-OF integer &optional RADIX (radix 10)) "Iterate `var` through the digits of `integer` in base `radix`, low-order first." (let ((kwd (if generate 'generate 'for))) @@ -28,9 +38,11 @@ (defun digits-to-number (digits) - (reduce (lambda (total digit) - (+ (* total 10) digit)) - digits)) + (if digits + (reduce (lambda (total digit) + (+ (* total 10) digit)) + digits) + 0)) (defun palindromep (n &optional (radix 10)) @@ -353,6 +365,9 @@ (= n (length sequence))) +(defun reverse-integer (n) + (digits-to-number (nreverse (digits n)))) + ;;;; Problems ----------------------------------------------------------------- (defun problem-1 () @@ -1641,9 +1656,42 @@ (for p2 = (drop 5 cards)) (counting (euler.poker::poker-hand-beats-p p1 p2)))) - - - +(defun problem-55 () + ;; If we take 47, reverse and add, 47 + 74 = 121, which is palindromic. + ;; + ;; Not all numbers produce palindromes so quickly. For example, + ;; + ;; 349 + 943 = 1292, + ;; 1292 + 2921 = 4213 + ;; 4213 + 3124 = 7337 + ;; + ;; That is, 349 took three iterations to arrive at a palindrome. + ;; + ;; Although no one has proved it yet, it is thought that some numbers, like + ;; 196, never produce a palindrome. A number that never forms a palindrome + ;; through the reverse and add process is called a Lychrel number. Due to the + ;; theoretical nature of these numbers, and for the purpose of this problem, + ;; we shall assume that a number is Lychrel until proven otherwise. In + ;; addition you are given that for every number below ten-thousand, it will + ;; either (i) become a palindrome in less than fifty iterations, or, (ii) no + ;; one, with all the computing power that exists, has managed so far to map it + ;; to a palindrome. In fact, 10677 is the first number to be shown to require + ;; over fifty iterations before producing a palindrome: + ;; 4668731596684224866951378664 (53 iterations, 28-digits). + ;; + ;; Surprisingly, there are palindromic numbers that are themselves Lychrel + ;; numbers; the first example is 4994. + ;; + ;; How many Lychrel numbers are there below ten-thousand? + (labels ((lychrel (n) + (+ n (reverse-integer n))) + (lychrelp (n) + (iterate + (repeat 50) + (for i :iterating #'lychrel :initially n) + (never (palindromep i))))) + (iterate (for i :from 0 :below 10000) + (counting (lychrelp i))))) (defun problem-56 () ;; A googol (10^100) is a massive number: one followed by one-hundred zeros; @@ -1656,6 +1704,33 @@ (b :from 1 :below 100))) (maximizing (funcall #'sum (digits (expt a b)))))) +(defun problem-57 () + ;; It is possible to show that the square root of two can be expressed as an + ;; infinite continued fraction. + ;; + ;; √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213... + ;; + ;; By expanding this for the first four iterations, we get: + ;; + ;; 1 + 1/2 = 3/2 = 1.5 + ;; 1 + 1/(2 + 1/2) = 7/5 = 1.4 + ;; 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... + ;; 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379... + ;; + ;; The next three expansions are 99/70, 239/169, and 577/408, but the eighth + ;; expansion, 1393/985, is the first example where the number of digits in the + ;; numerator exceeds the number of digits in the denominator. + ;; + ;; In the first one-thousand expansions, how many fractions contain + ;; a numerator with more digits than denominator? + (iterate + (repeat 1000) + (for i :initially 1/2 :then (/ (+ 2 i))) + (for expansion = (1+ i)) + (counting (> (digits-length (numerator expansion)) + (digits-length (denominator expansion)))))) + + (defun problem-74 () ;; The number 145 is well known for the property that the sum of the factorial ;; of its digits is equal to 145: @@ -1703,13 +1778,11 @@ ;; There are 120 reversible numbers below one-thousand. ;; ;; How many reversible numbers are there below one-billion (10^9)? - (labels ((reverse-integer (n) - (digits-to-number (nreverse (digits n)))) - (reversiblep (n) - (let ((reversed (reverse-integer n))) - (values (unless (zerop (digit 0 n)) - (every #'oddp (digits (+ n reversed)))) - reversed)))) + (flet ((reversiblep (n) + (let ((reversed (reverse-integer n))) + (values (unless (zerop (digit 0 n)) + (every #'oddp (digits (+ n reversed)))) + reversed)))) (iterate ;; TODO: improve this one ;; (with limit = 1000000000) there are no 9-digit reversible numbers... @@ -1781,8 +1854,10 @@ (test p52 (is (= 142857 (problem-52)))) (test p53 (is (= 4075 (problem-53)))) (test p54 (is (= 376 (problem-54)))) +(test p55 (is (= 249 (problem-55)))) +(test p56 (is (= 972 (problem-56)))) +(test p57 (is (= 153 (problem-57)))) -(test p56 (is (= 972 (problem-56)))) (test p74 (is (= 402 (problem-74)))) (test p145 (is (= 608720 (problem-145))))