Commits

Anonymous committed d787df1

Updated after solving some more

  • Participants
  • Parent commits 5d124bd

Comments (0)

Files changed (1)

 ;;   (debug (parse-integer (apply str (reverse (format "%d" x)))))
   (parse-integer (apply str (reverse (format "%d" x)))))
 
+(defn num-reverse [x]
+;;   (debug x)
+;;   (debug (format "%d" x))
+;;   (debug (reverse (format "%d" x)))
+;;   (debug (apply str (reverse (format "%d" x))))
+;;   (debug (parse-integer (apply str (reverse (format "%d" x)))))
+  (parse-big-integer (apply str (reverse (format "%d" x)))))
+
 (defn palindrome? [x]
   (= x (num-reverse x)))
 
                      (63 66  4 68 89 53 67 30 73 16 69 87 40 31)
                      ( 4 62 98 27 23  9 70 98 73 93 38 53 60  4 23)
                      ))
-;; NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
-
+;; NOTE: As there are only 16384 routes, it is possible to solve this
+;; problem by trying every route. However, Problem 67, is the same
+;; challenge with a triangle containing one-hundred rows; it cannot be
+;; solved by brute force, and requires a clever method! ;o)
 
 (defn path-helper [accum triangle]
   (if (nil? triangle)
 
 ;; Euler published the remarkable quadratic formula:
 
-;; n + n + 41
+;; n² + n + 41
 
 ;; It turns out that the formula will produce 40 primes for the
 ;; consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41
 ;; = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41
-;; 41� + 41 + 41 is clearly divisible by 41.
-
-;; Using computers, the incredible formula n� - 79n + 1601 was discovered
+;; 41² + 41 + 41 is clearly divisible by 41.
+
+;; Using computers, the incredible formula n² - 79n + 1601 was discovered
 ;; which produces 80 primes for the consecutive values n = 0 to 79. The
 ;; product of the coefficients, -79 and 1601, is -126479.
 
 ;; Considering quadratics of the form:
 
-;; n + an + b, where |a|  1000 and |b|  1000
+;; n² + an + b, where |a|  1000 and |b|  1000
 
 ;; where |n| is the modulus/absolute value of n
 ;; e.g. |11| = 11 and |-4| = 4
 ;}}}
 ;{{{ problem 31 -- currency
 
-;; In England the currency is made up of pound, , and pence, p, and
+;; In England the currency is made up of pound, £, and pence, p, and
 ;; there are eight coins in general circulation:
 
-;; 1p, 2p, 5p, 10p, 20p, 50p, 1 (100p) and 2 (200p).
+;; 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
 
 (def denominations '(200 100 50 20 10 5 2 1))
 
-;; It is possible to make �2 in the following way:
-
-;; 1�1 + 150p + 220p + 15p + 12p + 31p
-;; How many different ways can �2 be made using any number of coins?
+;; It is possible to make £2 in the following way:
+
+;; 1£1 + 150p + 220p + 15p + 12p + 31p
+;; How many different ways can £2 be made using any number of coins?
 
 (defn coins [value denominations]
 ;;   (println value denominations (range (inc (/ value (first denominations)))))
 ;{{{ problem 42 -- triangle words
 
 ;; The nth term of the sequence of triangle numbers is given by, tn =
-;; n(n+1); so the first ten triangle numbers are:
+;; ½n(n+1); so the first ten triangle numbers are:
 
 ;; 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
 
   (let [digits (to-digits n)]
     (every? zero?
             (map (fn [x p]
-                   (rem (big-parse-integer (apply str (take 3 (nthrest digits x)))) p))
+                   (rem (parse-big-integer (apply str (take 3 (nthrest digits x)))) p))
                  (range 1 8)
                  primes))))
 
   (take 4
 ;;   (reduce +
           (filter substring-divisible?
-                  (map #(big-parse-integer (apply str %))
+                  (map #(parse-big-integer (apply str %))
                        (drop (factorial 9) ;The first 9! are too small
                              (permutations "0123456789"))))))
 
   (and (not (zero? (first seq)))
        (every? zero?
                (map (fn [x p]
-;;                       (prn x p (big-parse-integer (apply str (take 3 (nthrest seq x)))) (rem (big-parse-integer (apply str (take 3 (nthrest seq x)))) p))
-                      (rem (big-parse-integer (apply str (take 3 (nthrest seq x)))) p))
+;;                       (prn x p (parse-big-integer (apply str (take 3 (nthrest seq x)))) (rem (parse-big-integer (apply str (take 3 (nthrest seq x)))) p))
+                      (rem (parse-big-integer (apply str (take 3 (nthrest seq x)))) p))
                     (range 1 8)
                     primes))))
 
 
 ;; The first three consecutive numbers to have three distinct prime factors are:
 
-;; 644 = 2  7  23
+;; 644 = 2²  7  23
 ;; 645 = 3  5  43
 ;; 646 = 2  17  19.
 
 ;}}}
 ;}}}
 
-;{{{ problem 51 -- prime replace gives prime
+;{{{ problem 51 -- prime replace gives prime *
 
 ;; By replacing the 1st digit of *57, it turns out that six of the
 ;; possible values: 157, 257, 457, 557, 757, and 857, are all prime.
 ;; Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x
 ;; and 6x, contain the same digits.
 
+(defn have-same-digits? [n]
+  (apply = (map #(sort (to-digits (* n %))) (range 2 7))))
+
+(defn find-same-digits []
+  (first
+        (filter have-same-digits? (iterate inc 1))))
+
+;; (find-same-digits)
+;; 142857
 
 ;}}}
 ;{{{ problem 52 -- n Choose r > 1 M
 ;; How many, not necessarily distinct, values of nCr, for 1 n 100, are
 ;; greater than one-million?
 
+(defn big-chooses [x min]
+  (count (filter #(> % min)
+                 (for [n (range 1 (inc x))
+                       r (range 1 (inc x))]
+                   (choose n r)))))
+
+;; (big-chooses 100 1000000)
+;; 4075
+
 ;}}}
 ;{{{ problem 54 -- poker hands
 
 ;; Straight Flush: All cards are consecutive values of same suit.
 ;; Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.
 
+(defn high-card [hand]
+  (ffirst hand))
+
+(defn high-card-compare [p1 p2]
+  (. (high-card p1) (compareTo (high-card p2))))
+
+(defn flush? [hand]
+  (= 1 (count (distinct (map frest hand)))))
+
+(defn straight? [hand]
+  (let [h (high-card hand)]
+    (= (reverse (map first hand))
+       (range (- h 4) (inc h)))))
+
+(defn straight-flush? [hand]
+  (and (straight? hand)
+       (flush? hand)))
+
+(defn royal-flush? [hand]
+  (and (straight-flush? hand)
+       (= 14 (high-card hand))))
+
+(defn get-tuples [hand]
+  (reverse (sort-by frest ;; TODO: ensure this is a stable sort
+                    (reverse (run-length-encode (map first hand))))))
+
+(defn num-same [hand]
+  (filter #(> % 1)
+          (map frest (get-tuples hand))))
+
+(defn high-tuple-card-compare [p1 p2]
+  (let [h1 (map first (get-tuples p1))
+        h2 (map first (get-tuples p2))]
+    (first (filter (complement zero?)
+                   (map (fn [x y] (. x (compareTo y)))
+                        h1 h2)))))
+
+(defn poker-compare [p1 p2]
+  (cond (royal-flush? p1)
+          (if (royal-flush? p2) 0 1)      ;this would be a tie and we are guaranteed none
+        (royal-flush? p2)
+          -1
+        (straight-flush? p1)
+          (if (straight-flush? p2) (high-card-compare p1 p2) 1)
+        (straight-flush? p2)
+          -1
+        (= '(4) (num-same p1))
+          (if (= '(4) (num-same p2)) (high-tuple-card-compare p1 p2) 1)
+        (= '(4) (num-same p2))
+          -1
+        (= '(3 2) (num-same p1))
+          (if (= '(3 2) (num-same p2)) (high-tuple-card-compare p1 p2) 1)
+        (= '(3 2) (num-same p2))
+          -1
+        (flush? p1)
+          (if (flush? p2) (high-card-compare p1 p2) 1)
+        (flush? p2)
+          -1
+        (straight? p1)
+          (if (straight? p2) (high-card-compare p1 p2) 1)
+        (straight? p2)
+          -1
+        (= '(3) (num-same p1))
+          (if (= '(3) (num-same p2)) (high-tuple-card-compare p1 p2) 1)
+        (= '(3) (num-same p2))
+          -1
+        (= '(2 2) (num-same p1))
+          (if (= '(2 2) (num-same p2)) (high-tuple-card-compare p1 p2) 1)
+        (= '(2 2) (num-same p2))
+          -1
+        (= '(3) (num-same p1))
+          (if (= '(3) (num-same p2)) (high-tuple-card-compare p1 p2) 1)
+        (= '(3) (num-same p2))
+          -1
+        (= '(2) (num-same p1))
+          (if (= '(2) (num-same p2)) (high-tuple-card-compare p1 p2) 1)
+        (= '(2) (num-same p2))
+          -1
+        :else
+          (high-card-compare p1 p2)))
+
 ;; The cards are valued in the order:
 ;; 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.
 
 
 ;; Consider the following five hands dealt to two players:
 
-;; Hand	 	Player 1	 	Player 2	 	Winner
-;; 1	 	5H 5C 6S 7S KD
+;; Hand     Player 1        Player 2        Winner
+;; 1        5H 5C 6S 7S KD
 ;; Pair of Fives
-;;  	2C 3S 8S 8D TD
+;;      2C 3S 8S 8D TD
 ;; Pair of Eights
-;;  	Player 2
-
-;; 2	 	5D 8C 9S JS AC
+;;      Player 2
+
+;; 2        5D 8C 9S JS AC
 ;; Highest card Ace
-;;  	2C 5C 7D 8S QH
+;;      2C 5C 7D 8S QH
 ;; Highest card Queen
-;;  	Player 1
-
-;; 3	 	2D 9C AS AH AC
+;;      Player 1
+
+;; 3        2D 9C AS AH AC
 ;; Three Aces
-;;  	3D 6D 7D TD QD
+;;      3D 6D 7D TD QD
 ;; Flush with Diamonds
-;;  	Player 2
-
-;; 4	 	4D 6S 9H QH QC
+;;      Player 2
+
+;; 4        4D 6S 9H QH QC
 ;; Pair of Queens
 ;; Highest card Nine
-;;  	3D 6D 7H QD QS
+;;      3D 6D 7H QD QS
 ;; Pair of Queens
 ;; Highest card Seven
-;;  	Player 1
-
-;; 5	 	2H 2D 4C 4D 4S
+;;      Player 1
+
+;; 5        2H 2D 4C 4D 4S
 ;; Full House
 ;; With Three Fours
-;;  	3C 3D 3S 9S 9D
+;;      3C 3D 3S 9S 9D
 ;; Full House
 ;; with Three Threes
-;;  	Player 1
+;;      Player 1
 
 ;; The file, poker.txt, contains one-thousand random hands dealt to
 ;; two players. Each line of the file contains ten cards (separated by
 
 ;; How many hands does Player 1 win?
 
-
+;; Cards will look like '(num suit)
+(defn parse-card [card]
+  (let [num (first card)
+        suit (frest card)]
+
+    ;; The cards are valued in the order:
+    ;; 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.
+    (list (cond (= num \T) 10
+                (= num \J) 11
+                (= num \Q) 12
+                (= num \K) 13
+                (= num \A) 14
+                :else      (parse-integer (str num)))
+          suit)))
+
+(defn parse-poker-line [line]
+  (map parse-card (re-seq #"[^ ]+" line)))
+
+(defn poker [file]
+  (count (filter #(= % 1)
+                 (for [l (file-lines file)]
+                   (let [cards (parse-poker-line l)
+                         player1 (reverse (sort-by first (take 5 cards)))
+                         player2 (reverse (sort-by first (nthrest cards 5)))]
+;;                      (list player1 player2 (poker-compare player1 player2))
+                     (poker-compare player1 player2)
+                     )))))
+
+;; (poker "poker.txt")
+;; 376
 
 ;}}}
 ;{{{ problem 55 -- Lychrel numbers
 ;; NOTE: Wording was modified slightly on 24 April 2007 to emphasise
 ;; the theoretical nature of Lychrel numbers.
 
-
+(defn lychrel? [n]
+  ((fn [n iterations]
+     (cond (> iterations 50)
+             true
+           (palindrome? n)
+             false
+           :else
+             (recur (+ n (num-reverse n)) (inc iterations))))
+   (+ n (num-reverse n)) 0))
+
+(defn how-many-lychrels [n]
+  (count (filter lychrel? (range 0 n))))
+
+;; (how-many-lychrels 10000)
+;; 249
 
 ;}}}
 ;{{{ problem 56 -- digital sums of powers
 ;; Considering natural numbers of the form, a^b, where a, b < 100, what
 ;; is the maximum digital sum?
 
+(defn digital-sums-of-powers [n]
+  (reduce max (for [a (range 1 n)
+                    b (range 1 n)]
+                (sum-of-digits (big-integer-pow a b)))))
+
+;; (digital-sums-of-powers 100)
+;; 972
 
 ;}}}
 ;{{{ problem 57 -- continued fractions
 ;; In the first one-thousand expansions, how many fractions contain a
 ;; numerator with more digits than denominator?
 
-
+(defn continued-fractions [x limit accum]
+  (if (zero? limit)
+    accum
+    (let [next-n (inc (/ (inc x)))
+          next-accum (if (> (count (to-digits (. x numerator)))
+                            (count (to-digits (. x denominator))))
+                       (inc accum) accum)]
+      (recur next-n (dec limit) next-accum))))
+
+;; (continued-fractions 3/2 1000 0)
+;; 153
 
 ;}}}
 ;{{{ problem 58 -- prime spiral arms
 ;; continued, what is the side length of the square spiral for which
 ;; the ratio of primes along both diagonals first falls below 10%?
 
+
+;; We have 1, +2,+2,+2,+2, +4,+4,+4,+4, etc.
+
+(def spiral-diagonals
+     (lazy-cons 1
+                ((fn this[cur amt]
+                  (let [new-seq (map #(+ cur (* amt %)) (range 1 5))]
+                    (lazy-cat (map #(+ cur (* amt %)) (range 1 5))
+                              (this (nth new-seq 3) (+ 2 amt)))))
+                 1 2)))
+
+(def spiral-diagonals
+     (lazy-cons '(1)
+                ((fn this[cur amt]
+                  (let [new-seq (map #(+ cur (* amt %)) (range 1 5))]
+                    (lazy-cons (map #(+ cur (* amt %)) (range 1 5))
+                              (this (nth new-seq 3) (+ 2 amt)))))
+                 1 2)))
+
+(defn bob [n]
+  (take n
+        (map (fn [diags len cnt]
+               (list (count (filter isprime? (distinct diags))) len cnt)) ;(if (isprime? d) 1 0)
+             spiral-diagonals
+             (iterate #(+ 2 %) 1)
+             (iterate #(+ 4 %) 1))))
+
+
+(defn find-spiral-prime-ratio [ratio]
+  ((fn this[diags primes cnt len]
+     (let [cur-primes (+ primes (count (filter isprime? (first diags))))
+           cur-cnt (+ 4 cnt)
+           cur-len (+ 2 len)]
+       (if (< (/ cur-primes cur-cnt) ratio)
+         cur-len
+         (recur (rest diags) cur-primes cur-cnt cur-len))))
+   (drop 1 spiral-diagonals) 0 1 1))
+
+;; (find-spiral-prime-ratio 1/10)
+;; 26241
+
 ;}}}
 ;{{{ problem 59 -- encryption
 
 ;; English words, decrypt the message and find the sum of the ASCII
 ;; values in the original text.
 
+(defn max-frest
+  ([a] a)
+  ([a b] (if (< (frest a) (frest b)) b a)))
+
+(defn find-key [seq]
+  (let [rle (run-length-encode (sort seq))
+        most-popular (first (reduce max-frest rle))]
+    (bit-xor most-popular (int \space )))) ; All too easy -- didn't really solve the problem though...
+
+(defn map-no-exhaust [f & seqs]
+  (lazy-cons (apply f (map first seqs))
+   (if (every? nil? (map first seqs))
+     nil
+     (apply map-no-exhaust f (map rest seqs)))))
+
+(defn decipher-xor [file n]
+  (let [numbers (re-seq #"\d+" (slurp file))]
+    (apply str
+           (apply map-no-exhaust str ; This doesn't find all the input since it only uses sequences while they all have data
+                  (for [x (range n)]
+                    (let [stream (map parse-integer (take-nth n (drop x numbers)))
+                          key (find-key stream)]
+                      (map #(char (bit-xor key %)) stream)))))))
+
+;; (reduce + (map int (decipher-xor "cipher1.txt" 3)))
+;; 107359
 
 ;}}}
-;{{{ problem 60 -- prime concatenation
+;{{{ problem 60 -- prime concatenation *
 
 ;; The primes 3, 7, 109, and 673, are quite remarkable. By taking any
 ;; two primes and concatenating them in any order the result will
 ;; Find the lowest sum for a set of five primes for which any two
 ;; primes concatenate to produce another prime.
 
-
+(def primes-concatenated {})
+(defn prime-concatenation [n]
+;;   (sort-by first
+  (let [primes-concatenated {}]
+    (for [p1 (primes-below n)
+          p2 (primes-below p1) :when (and (isprime? (int-concat p1 p2))
+                                          (isprime? (int-concat p2 p1)))]
+      (do
+        (update-in primes-concatenated [p1]
+                   #(cons p2 %))
+        (update-in primes-concatenated [p2]
+                   #(cons p1 %))
+        (update-in primes-concatenated [p1]
+                   #(cons p2 %))))
+    primes-concatenated))
 
 ;}}}
+
+;{{{ problem 61 -- cyclic figurate numbers *
+
+;; Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal
+;; numbers are all figurate (polygonal) numbers and are generated by
+;; the following formulae:
+
+;; Triangle         P3,n=n(n+1)/2        1, 3, 6, 10, 15, ...
+;; Square           P4,n=n^2             1, 4, 9, 16, 25, ...
+;; Pentagonal       P5,n=n(3n-1)/2       1, 5, 12, 22, 35, ...
+;; Hexagonal        P6,n=n(2n-1)         1, 6, 15, 28, 45, ...
+;; Heptagonal       P7,n=n(5n-3)/2       1, 7, 18, 34, 55, ...
+;; Octagonal        P8,n=n(3n-2)         1, 8, 21, 40, 65, ...
+
+;; The ordered set of three 4-digit numbers: 8128, 2882, 8281, has
+;; three interesting properties.
+
+;; The set is cyclic, in that the last two digits of each number is
+;; the first two digits of the next number (including the last number
+;; with the first).
+
+;; Each polygonal type: triangle (P3,127=8128), square (P4,91=8281)
+;; and pentagonal (P5,44=2882), is represented by a different number
+;; in the set.
+
+;; This is the only set of 4-digit numbers with this property.
+
+;; Find the sum of the only ordered set of six cyclic 4-digit numbers
+;; for which each polygonal type: triangle, square, pentagonal
+;; hexagonal, heptagonal, and octagonal, is represented by a different
+;; number in the set.
+
+
+
+;}}}
+;{{{ problem 62 -- permuting cubes
+
+;; The cube, 41063625 (345^3), can be permuted to produce two other
+;; cubes: 56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is
+;; the smallest cube which has exactly three permutations of its
+;; digits which are also cube.
+
+;; Find the smallest cube for which exactly five permutations of its digits are cube.
+
+(defn permutations-with-repeats [seq]
+  ;;   (prn 'seq seq)
+  (if (= 1 (count seq))
+    (list seq)
+    (apply concat (for [x (distinct seq)]
+                    (do
+;;                       (prn 'x x)
+                      (let [tail (filter #(not= x %) seq)
+                            repeats (dec (count (filter #(= x %) seq)))
+                            real-tail (concat tail (take repeats (repeat x)))]
+
+;;                         (prn 'repeats repeats 'real-tail real-tail 'tail tail 'perm (permutations-with-repeats tail))
+                        (map #(cons x %)
+                             (permutations-with-repeats real-tail))))))))
+
+(def cubes (map #(* % % %) (iterate inc 1)))
+
+(defn cube? [n]
+  (let [x (Math/round (Math/pow n 1/3))]
+    (= (* x x x) n)))
+
+(defn num-permuted-cubes [n]
+  (prn 'num-permuted-cubes n)
+  (count (filter #(and (>= % n) (cube? %))
+                 (map #(apply int-concat %)
+                      (permutations-with-repeats (to-digits n))))))
+
+(defn smallest-permutable-cube [n]
+  (first (filter #(= n (num-permuted-cubes %))
+                  cubes)))
+
+(defn smallest-permutable [limit seq]
+  ((fn this [m seq]
+     (let [n (first seq)
+           sorted-digits (sort (to-digits n))
+           new-map (update-in m [sorted-digits] #(cons n %))]
+       (if (and (= limit (count (new-map sorted-digits)))
+;;                 (= 1 (num-permuted-cubes n)) ;; just to make sure it's exactly 5... (because this only counts those >= self)
+                )
+         (reduce min (new-map sorted-digits)) ;; This isn't actually the smallest
+         (recur new-map (rest seq)))))
+   {} seq))
+
+;; (smallest-permutable 5 cubes)
+;; 127035954683
+
+;}}}
+;{{{ problem 63 -- n-digit n-th powers
+
+;; The 5-digit number, 16807=7^5, is also a fifth power. Similarly
+;; the 9-digit number, 134217728=8^9, is a ninth power.
+
+;; How many n-digit positive integers exist which are also an nth power?
+
+(defn n-digit-nth-powers-of [n]
+  ((fn this [n power num-digits accum]
+;;      (prn n power num-digits (count accum))
+;;      (flush)
+     (cond (= num-digits (count (to-digits power)))
+             (recur n (* n power) (inc num-digits) (cons power accum))
+;;            (> num-digits 100)
+;;              accum
+;;            (< num-digits (count (to-digits power)))
+;;              (recur n (* n power) (inc num-digits) accum)
+           :else
+             accum))
+   n n 1 '()))
+
+
+;; TODO: maybe I should make a map from sorted digits of cubes and
+;; check everytime to see if there are 5, etc.
+(defn num-n-digit-nth-powers []
+  (count (distinct (mapcat n-digit-nth-powers-of (range 1 10)))))
+
+;; (num-n-digit-nth-powers)
+;; 49
+
+;}}}
+;{{{ problem 64 -- periods of continued fractions *
+
+;; All square roots are periodic when written as continued fractions
+;; and can be written in the form:
+
+;; N = a0 +
+;; 1
+;;      a1 +
+;; 1
+;;          a2 +
+;; 1
+;;              a3 + ...
+;; For example, let us consider 23:
+
+;; 23 = 4 + 23 - 4 = 4 +
+;; 1
+;;  = 4 +
+;; 1
+
+;; 1
+;; 23-4
+;;      1 +
+;; 23 - 3
+;; 7
+;; If we continue we would get the following expansion:
+
+;; 23 = 4 +
+;; 1
+;;      1 +
+;; 1
+;;          3 +
+;; 1
+;;              1 +
+;; 1
+;;                  8 + ...
+;; The process can be summarised as follows:
+
+;; a0 = 4
+;; 1
+;; 23-4
+;;  =
+;; 23+4
+;; 7
+;;  = 1 +
+;; 23-3
+;; 7
+;; a1 = 1
+;; 7
+;; 23-3
+;;  =
+;; 7(23+3)
+;; 14
+;;  = 3 +
+;; 23-3
+;; 2
+;; a2 = 3
+;; 2
+;; 23-3
+;;  =
+;; 2(23+3)
+;; 14
+;;  = 1 +
+;; 23-4
+;; 7
+;; a3 = 1
+;; 7
+;; 23-4
+;;  =
+;; 7(23+4)
+;; 7
+;;  = 8 +   23-4
+;; a4 = 8
+;; 1
+;; 23-4
+;;  =
+;; 23+4
+;; 7
+;;  = 1 +
+;; 23-3
+;; 7
+;; a5 = 1
+;; 7
+;; 23-3
+;;  =
+;; 7(23+3)
+;; 14
+;;  = 3 +
+;; 23-3
+;; 2
+;; a6 = 3
+;; 2
+;; 23-3
+;;  =
+;; 2(23+3)
+;; 14
+;;  = 1 +
+;; 23-4
+;; 7
+;; a7 = 1
+;; 7
+;; 23-4
+;;  =
+;; 7(23+4)
+;; 7
+;;  = 8 +   23-4
+;; It can be seen that the sequence is repeating. For conciseness, we
+;; use the notation 23 = [4;(1,3,1,8)], to indicate that the block
+;; (1,3,1,8) repeats indefinitely.
+
+;; The first ten continued fraction representations of (irrational) square roots are:
+
+;; 2=[1;(2)], period=1
+;; 3=[1;(1,2)], period=2
+;; 5=[2;(4)], period=1
+;; 6=[2;(2,4)], period=2
+;; 7=[2;(1,1,1,4)], period=4
+;; 8=[2;(1,4)], period=2
+;; 10=[3;(6)], period=1
+;; 11=[3;(3,6)], period=2
+;; 12= [3;(2,6)], period=2
+;; 13=[3;(1,1,1,1,6)], period=5
+
+;; Exactly four continued fractions, for N  13, have an odd period.
+
+;; How many continued fractions for N  10000 have an odd period?
+
+
+;}}}
+;{{{ problem 65 -- continued fractions for e
+
+;; The square root of 2 can be written as an infinite continued fraction.
+
+;; 2 = 1 +
+;; 1
+;;      2 +
+;; 1
+;;          2 +
+;; 1
+;;              2 +
+;; 1
+;;                  2 + ...
+
+;; The infinite continued fraction can be written, 2 = [1;(2)], (2)
+;; indicates that 2 repeats ad infinitum. In a similar way, sqrt(23) =
+;; [4;(1,3,1,8)].
+
+;; It turns out that the sequence of partial values of continued
+;; fractions for square roots provide the best rational
+;; approximations. Let us consider the convergents for 2.
+
+;; 1 +
+;; 1/2
+;; = 3/2
+
+;; 1 +
+;; 1
+;; = 7/5
+;;      2 +
+;; 1
+
+;; 2
+;; 1 +
+;; 1
+;; = 17/12
+;;      2 +
+;; 1
+
+;;          2 +
+;; 1
+
+
+
+;; 2
+
+;; 1 +
+;; 1
+
+;; = 41/29
+;;      2 +
+;; 1
+
+;;          2 +
+;; 1
+
+
+;;              2 +
+;; 1
+
+
+
+;; 2
+
+;; Hence the sequence of the first ten convergents for sqrt(2) are:
+
+;; 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
+;; What is most surprising is that the important mathematical constant
+;; e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].
+
+;; The first ten terms in the sequence of convergents for e are:
+
+;; 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
+;; The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.
+
+;; Find the sum of digits in the numerator of the 100th convergent of
+;; the continued fraction for e.
+
+(def continued-fraction-e
+     (lazy-cons 2
+                ((fn this[n]
+                  (lazy-cat (list 1 n 1)
+                            (this (+ 2 n))))
+                 2)))
+
+(defn continued-fraction-nth-convergent [seq limit]
+  (/ ((fn this[seq accum]
+        (if seq
+           (recur (rest seq) (/ (+ (first seq) accum)))
+          accum))
+      (reverse (take limit seq)) 0)))
+
+(defn nth-e-convergent [n]
+  (sum-of-digits (. (continued-fraction-nth-convergent continued-fraction-e n) numerator)))
+
+;; (nth-e-convergent 100)
+;; 272
+
+;}}}
+;{{{ problem 66 -- Diaphontine equations *
+
+;; Consider quadratic Diophantine equations of the form:
+
+;; x^2 - Dy^2 = 1
+
+;; For example, when D=13, the minimal solution in x is 6492 - 131802 = 1.
+
+;; It can be assumed that there are no solutions in positive integers
+;; when D is square.
+
+;; By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we
+;; obtain the following:
+
+;; 3^2 - 2*2^2 = 1
+;; 2^2 - 3*1^2 = 1
+;; 9^2 - 5*4^2 = 1  <--
+;; 5^2 - 6*2^2 = 1
+;; 8^2 - 7*3^2 = 1
+
+;; Hence, by considering minimal solutions in x for D <= 7, the largest x
+;; is obtained when D=5.
+
+;; Find the value of D <= 1000 in minimal solutions of x for which the
+;; largest value of x is obtained.
+
+;}}}
+;{{{ problem 67 -- more triangle path maximizing
+
+;; By starting at the top of the triangle below and moving to adjacent
+;; numbers on the row below, the maximum total from top to bottom is
+;; 23.
+
+;; 3
+;; 7 5
+;; 2 4 6
+;; 8 5 9 3
+
+;; That is, 3 + 7 + 4 + 9 = 23.
+
+;; Find the maximum total from top to bottom in triangle.txt (right
+;; click and 'Save Link/Target As...'), a 15K text file containing a
+;; triangle with one-hundred rows.
+
+;; NOTE: This is a much more difficult version of Problem 18. It is
+;; not possible to try every route to solve this problem, as there are
+;; 299 altogether! If you could check one trillion (1012) routes every
+;; second it would take over twenty billion years to check them
+;; all. There is an efficient algorithm to solve it. ;o)
+
+(defn path-maximizer [file]
+  (path-helper nil
+               (map #(map parse-integer (re-seq #"\d+" %))
+                    (file-lines file))))
+
+;; (path-maximizer "triangle.txt")
+;; 7273
+
+;}}}
+;{{{ problem 68 -- magic n-gons *
+
+;; Consider the following "magic" 3-gon ring, filled with the numbers
+;; 1 to 6, and each line adding to nine.
+
+;;     4
+;;     |
+;; 5-1-3
+;;    \|
+;;     2
+;;       \
+;;        6
+
+;; Working clockwise, and starting from the group of three with the
+;; numerically lowest external node (4,3,2 in this example), each
+;; solution can be described uniquely. For example, the above solution
+;; can be described by the set: 4,3,2; 6,2,1; 5,1,3.
+
+;; It is possible to complete the ring with four different totals: 9
+;; 10, 11, and 12. There are eight solutions in total.
+
+;; Total	Solution Set
+;; 9	4,2,3; 5,3,1; 6,1,2
+;; 9	4,3,2; 6,2,1; 5,1,3
+;; 10	2,3,5; 4,5,1; 6,1,3
+;; 10	2,5,3; 6,3,1; 4,1,5
+;; 11	1,4,6; 3,6,2; 5,2,4
+;; 11	1,6,4; 5,4,2; 3,2,6
+;; 12	1,5,6; 2,6,4; 3,4,5
+;; 12	1,6,5; 3,5,4; 2,4,6
+
+;; By concatenating each group it is possible to form 9-digit strings;
+;; the maximum string for a 3-gon ring is 432621513.
+
+;; Using the numbers 1 to 10, and depending on arrangements, it is
+;; possible to form 16- and 17-digit strings. What is the maximum
+;; 16-digit string for a "magic" 5-gon ring?
+
+
+
+
+;}}}
+;{{{ problem 69 -- totient *
+
+;; Euler's Totient function, φ(n) [sometimes called the phi function]
+;; is used to determine the number of numbers less than n which are
+;; relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are
+;; all less than nine and relatively prime to nine, φ(9)=6.
+
+;; n    Relatively Prime  φ(n)   n/φ(n)
+;; 2      1               1      2
+;; 3      1,2             2      1.5
+;; 4      1,3             2      2
+;; 5      1,2,3,4         4      1.25
+;; 6      1,5             2      3
+;; 7      1,2,3,4,5,6     6      1.1666...
+;; 8      1,3,5,7         4      2
+;; 9      1,2,4,5,7,8     6      1.5
+;; 10     1,3,7,9         4      2.5
+
+;; It can be seen that n=6 produces a maximum n/φ(n) for n <= 10.
+
+;; Find the value of n <= 1,000,000 for which n/φ(n) is a maximum.
+
+(defn totient [n]                       ; TODO: this isn't quite right... I have to take repeated factors into account
+  (reduce * (map #(- % 1) (factors n))))
+
+
+;}}}
+;{{{ problem 70 -- totient *
+
+;; Euler's Totient function, φ(n) [sometimes called the phi function]
+;; is used to determine the number of positive numbers less than or
+;; equal to n which are relatively prime to n. For example, as 1, 2
+;; 4, 5, 7, and 8, are all less than nine and relatively prime to
+;; nine, φ(9)=6.
+
+;; The number 1 is considered to be relatively prime to every positive
+;; number, so φ(1)=1.
+
+;; Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
+
+;; Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
+
+;; (map #(list % (totient %))
+;;      (range 2 10000000))
+
+;}}}