# c856e5034f79

`Problem 25`
author Steve Losh Wed, 22 Feb 2017 13:14:22 +0000 d7c65f771582 d84ef3399dd1 (none) src/euler.lisp

## Changes

```--- a/src/euler.lisp	Wed Feb 22 12:41:39 2017 +0000
+++ b/src/euler.lisp	Wed Feb 22 13:14:22 2017 +0000
@@ -91,6 +91,24 @@
(counting t)))

+(defmacro-driver (FOR var IN-FIBONACCI _)
+  (declare (ignore _))
+  (with-gensyms (a b)
+    (let ((kwd (if generate 'generate 'for)))
+      `(progn
+         (with ,a = 0)
+         (with ,b = 1)
+         (,kwd ,var :next (prog1 ,b
+                            (psetf ,a ,b
+                                   ,b (+ ,a ,b))))))))
+
+(defun fibonacci (n)
+  "Return the first `n` Fibonacci numbers as a fresh list."
+  (iterate (repeat n)
+           (for i :in-fibonacci t)
+           (collect i)))
+
+
(defun binomial-coefficient (n k)
"Return `n` choose `k`."
;; https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
@@ -660,6 +678,34 @@
(sort <> #'<)
(elt <> (1- 1000000))))

+(defun problem-25 ()
+  ;; The Fibonacci sequence is defined by the recurrence relation:
+  ;;
+  ;;   Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
+  ;;
+  ;; Hence the first 12 terms will be:
+  ;;
+  ;; F1 = 1
+  ;; F2 = 1
+  ;; F3 = 2
+  ;; F4 = 3
+  ;; F5 = 5
+  ;; F6 = 8
+  ;; F7 = 13
+  ;; F8 = 21
+  ;; F9 = 34
+  ;; F10 = 55
+  ;; F11 = 89
+  ;; F12 = 144
+  ;;
+  ;; The 12th term, F12, is the first term to contain three digits.
+  ;;
+  ;; What is the index of the first term in the Fibonacci sequence to contain
+  ;; 1000 digits?
+  (iterate (for f :in-fibonacci t)
+           (for i :from 1)
+           (finding i :such-that (= 1000 (digits-length f)))))
+

;;;; Tests --------------------------------------------------------------------
(def-suite :euler)
@@ -689,6 +735,7 @@
(test p22 (is (= 871198282 (problem-22))))
(test p23 (is (= 4179871 (problem-23))))
(test p24 (is (= 2783915460 (problem-24))))
+(test p25 (is (= 4782 (problem-25))))

;; (run! :euler)```