# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1488473443 0
# Node ID 6936c3316864e562500408ed4401827ef8968b36
# Parent  639c1d3616ceaaf30ccb92bdedf4d16d52b34a90
Problems 55 and 57

diff -r 639c1d3616ce -r 6936c3316864 src/euler.lisp
--- 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))))