# d84ef3399dd1

`Problem 26`
author Steve Losh Wed, 22 Feb 2017 17:13:41 +0000 c856e5034f79 404d59f863aa (none) src/euler.lisp src/primes.lisp

## Changes

```--- a/src/euler.lisp	Wed Feb 22 13:14:22 2017 +0000
+++ b/src/euler.lisp	Wed Feb 22 17:13:41 2017 +0000
@@ -132,6 +132,14 @@
(> n (sum (proper-divisors n))))

+(defun multiplicative-order (integer modulus)
+  "Return the multiplicative order of `integer` modulo `modulus`."
+  ;; https://en.wikipedia.org/wiki/Multiplicative_order
+  (iterate (for i :from 1)
+           (for v :first integer :then (* v integer))
+           (finding i :such-that (= 1 (mod v modulus)))))
+
+
;;;; Problems -----------------------------------------------------------------
(defun problem-1 ()
;; If we list all the natural numbers below 10 that are multiples of 3 or 5,
@@ -706,6 +714,30 @@
(for i :from 1)
(finding i :such-that (= 1000 (digits-length f)))))

+(defun problem-26 ()
+  ;; A unit fraction contains 1 in the numerator. The decimal representation of
+  ;; the unit fractions with denominators 2 to 10 are given:
+  ;;
+  ;; 1/2	= 	0.5
+  ;; 1/3	= 	0.(3)
+  ;; 1/4	= 	0.25
+  ;; 1/5	= 	0.2
+  ;; 1/6	= 	0.1(6)
+  ;; 1/7	= 	0.(142857)
+  ;; 1/8	= 	0.125
+  ;; 1/9	= 	0.(1)
+  ;; 1/10	= 	0.1
+  ;;
+  ;; Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can
+  ;; be seen that 1/7 has a 6-digit recurring cycle.
+  ;;
+  ;; Find the value of d < 1000 for which 1/d contains the longest recurring
+  ;; cycle in its decimal fraction part.
+  (iterate
+    ;; 2 and 5 are the only primes that aren't coprime to 10
+    (for i :in (set-difference (primes-below 1000) '(2 5)))
+    (finding i :maximizing (multiplicative-order 10 i))))
+

;;;; Tests --------------------------------------------------------------------
(def-suite :euler)```
```--- a/src/primes.lisp	Wed Feb 22 13:14:22 2017 +0000
+++ b/src/primes.lisp	Wed Feb 22 17:13:41 2017 +0000
@@ -163,8 +163,14 @@
(when (= seen n)
(return i))))))

+
(defun woodall (n)
(1- (* n (expt 2 n))))

(defun woodall-prime-p (n)
(primep (woodall n)))
+
+
+(defun coprimep (a b)
+  (= 1 (gcd a b)))
+```