# euler

committed dd35ee9

Added pipeline, min-first, and solved a few problems

# probs.clj

` ;;     (debug (divides? cur n))`
` ;;     (debug acc)`
` ;;     (debug (frest seq))`
`-    (if (< n cur)`
`-      acc`
`-      (if (divides? cur n)`
`-        (recur (/ n cur) (cons cur acc) seq)`
`-        (recur n acc (rest seq))`
`-        ))))`
`+    (cond (< n cur)`
`+            acc`
`+          (> (* cur cur) n)`
`+            (cons n acc)`
`+          (divides? cur n)`
`+            (recur (/ n cur) (cons cur acc) seq)`
`+          :else`
`+            (recur n acc (rest seq)))))`
` `
` (defn factors [n]`
`   (factors-rec n '() primes))`
`   (try (Integer/parseInt str)`
`        (catch NumberFormatException nfe 0)))`
` `
`-(defn parse-integer [str]`
`-  (Integer/parseInt str))`
`+;; (defn parse-integer [str]`
`+;;   (Integer/parseInt str))`
` `
` (defn parse-big-integer [str]`
`   (BigInteger. str))`
` `
` (defn sum-of-squares [seq]`
`   (reduce + 0 (map #(* % %) seq)))`
`+`
` (defn square-of-sum [seq]`
`   (let [x (reduce + 0 seq)]`
`     (* x x)))`
` `
`-`
` ;; (- (square-of-sum (range 101))`
` ;;    (sum-of-squares (range 101)))`
` `
` ;; 25164150`
` `
`-`
` ;; with a little help from http://mathworld.wolfram.com/PowerSum.html`
` (defn sum-of-squares-upto [n]`
`   (/ (+ (* 2 n n n) (* 3 n n) (* n)) 6))`
`   ([x y & more] (reduce max-first (max-first x y) more))`
`   )`
` `
`+(defn min-first`
`+  ([x] x)`
`+  ([x y] (if (> (first x) (first y)) y x))`
`+  ([x y & more] (reduce min-first (min-first x y) more))`
`+  )`
`+`
` (defn find-repeating-decimals [n]`
`   (reduce max-first`
`           (map #(list (num-repeating-decimals (/ %)) %)`
` ;; "Elapsed time: 1035.227 msecs"`
` ;; ((5482660 1560090 7042750 8602840))`
` `
`-`
` ;}}}`
` ;{{{ problem 45 -- triangle, pentagonal and hexagonal numbers`
` `
` `
` ;; Find the next triangle number that is also pentagonal and hexagonal.`
` `
`-`
`-`
` (defn hexagonal? [H]`
`   (let [D   (+ 1 (* 8 H))`
`         num (+ 1 (Math/sqrt D))]`
` ;; 7273`
` `
` ;}}}`
`-;{{{ problem 68 -- magic n-gons *`
`+;{{{ 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.`
` ;; possible to form 16- and 17-digit strings. What is the maximum`
` ;; 16-digit string for a "magic" 5-gon ring?`
` `
`-`
`-`
`+(defn permutations-summing-rec [n must-start must-finish seq accum]`
`+  (cond (= (count seq) 1)`
`+          (if (= n (+ must-start must-finish (first seq)))`
`+            (list (reverse (cons (list (first seq) must-start must-finish) accum)))`
`+            nil)`
`+        (< (count seq) 1)`
`+          (prn 'impossible)`
`+        :else`
`+          (for [x seq`
`+                y seq :when (and (not= x y)`
`+                                 (= n (+ must-start x y)))]`
`+            (apply concat`
`+                   (permutations-summing-rec n y must-finish`
`+                                             (filter #(and (not= x %)`
`+                                                           (not= y %)) seq)`
`+                                             (cons (list x must-start y)`
`+                                                   accum))))))`
`+`
`+(defn has-smallest-first? [seq]`
`+  (not (or (nil? seq)`
`+           (let [firsts (map first seq)`
`+                 ff (first firsts)]`
`+             (filter #(> ff %) firsts)))))`
`+`
`+(defn permutations-summing [seq]`
`+  (apply concat (for [x seq`
`+                      y seq :when (not= x y)`
`+                      z seq :when (and (not= z x) (not= z y))]`
`+                  (let [n (+ x y z)`
`+                        smaller-seq (filter #(and (not= x %)`
`+                                                  (not= y %)`
`+                                                  (not= z %)) seq)]`
`+                    (filter (complement nil?)`
`+                            (permutations-summing-rec n z y smaller-seq (list (list x y z))))))))`
`+`
`+(defn largest-n-gon [n]`
`+  (reduce max`
`+          (filter #(< % 10000000000000000)`
`+                  (map #(apply big-int-concat (apply concat %))`
`+                       (filter has-smallest-first?`
`+                               (permutations-summing (range 1 (inc (* 2 n)))))))))`
`+`
`+;; (largest-n-gon 3)`
`+;; 432621513`
`+`
`+;; (largest-n-gon 5)`
`+;; 6531031914842725 -- without 16 digit restraint => 28797161103104548`
` `
` ;}}}`
`-;{{{ problem 69 -- totient *`
`+;{{{ problem 69 -- totient quotient`
` `
` ;; Euler's Totient function, φ(n) [sometimes called the phi function]`
` ;; is used to determine the number of numbers less than n which are`
` `
` ;; 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))))`
`-`
`+(defn totient [n]`
`+  (if (= n 1)`
`+    1`
`+    (reduce * (map #(* (dec (first %))`
`+                       (big-integer-pow (first %) (dec (frest %))))`
`+                   (run-length-encode (factors n))))))`
`+`
`+(defn totient-quotient [n]`
`+  (reduce * (map #(/ % (dec %))`
`+                 (distinct (factors n)))))`
`+`
`+(defn max-totient-quotient [n]`
`+  (frest (reduce max-first`
`+                 (map #(list (totient-quotient %) %)`
`+                      (range 2 (inc n))))))`
`+`
`+;; (time (max-totient-quotient 1000000))`
`+;; "Elapsed time: 17440.532 msecs"`
`+;; 510510`
`+;; (factors 510510)`
` `
` ;}}}`
`-;{{{ problem 70 -- totient *`
`+;{{{ problem 70 -- permuted totient quotient`
` `
` ;; Euler's Totient function, φ(n) [sometimes called the phi function]`
` ;; is used to determine the number of positive numbers less than or`
` `
` ;; 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.`
`+;; 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))`
` `
`+(defn min-permuted-totient-quotient [n]`
`+  (frest (reduce min-first`
`+                 (map #(list (/ (frest %) (first %)) (frest %))`
`+                      (filter #(= (sort (to-digits (first %)))`
`+                                  (sort (to-digits (frest %))))`
`+                              (map #(list (totient %) %)`
`+                                   (range 2 n)))))))`
`+`
`+;; (time (min-permuted-totient-quotient 10000000))`
`+;; "Elapsed time: 502657.557 msecs"`
`+;; 8319823`
`+`
` ;}}}`
`+`
`+(defmacro pipeline`
`+  "Meant to facilitate long map filter reduce pipelines, especially`
`+indentation and unncessary nesting.  Each keyword is changed into a`
`+call to the function of the same name with the two arguments, 1 next`
`+item in the macro body and the result of pipeline applied recursively`
`+to the rest of the body."`
`+  [& body]`
`+  (let [one (and body (first body))`
`+        two (and body (rest body) (frest body))`
`+        three (and body (rest body) (rrest body))]`
`+    (if (keyword? one)`
`+      (if (nil? two)                    ;Or maybe I could check to see if two is keyword?`
`+          (list (symbol (name one))`
`+                `(pipeline ~@three))`
`+        (list (symbol (name one))`
`+              two`
`+              `(pipeline ~@three)))`
`+      `(do ~@body))))`
`+`
`+`
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.