# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1487783621 0
# Node ID d84ef3399dd13da1bbcc9800e749ec3be3a56618
# Parent  c856e5034f794ad8bd2c11faba9a93ca909f8f74
Problem 26

diff -r c856e5034f79 -r d84ef3399dd1 src/euler.lisp
--- 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)
diff -r c856e5034f79 -r d84ef3399dd1 src/primes.lisp
--- 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)))
+