# Commits

committed d787df1

Updated after solving some more

• Participants
• Parent commits 5d124bd

# probs.clj

` ;;   (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))`
`+`
`+;}}}`