Anonymous avatar Anonymous committed dd35ee9

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

Comments (0)

Files changed (1)

 ;;     (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.