Anonymous avatar Anonymous committed 90e55f1

More ports and some timings

Comments (0)

Files changed (1)

             (recur n acc (rest seq)))))
 
 (defn factors [n]
-  (factors-rec n '() primes))
+  (if (< n 0)
+      (factors-rec (- n) '(-1) primes)
+    (factors-rec n '() primes)))
 
 (defn largest-factor [n]
   (first (factors n)))
                          '(1 1))))
 
 (defn first-where [pred seq]
-  (cond (nil? seq)
+  (cond (not (seq seq))
           seq
         (pred (first seq))
           (first seq)
 ;; (982 983)
 
 ;}}}
-ported to here
 ;{{{ problem 27 -- quadratic prime generator
 
 ;; Euler published the remarkable quadratic formula:
 
 ;; 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
                  (< n (first seq))
                    nil
                  :else
-                   (recur n (rest seq)))))
+                   (recur n (next seq)))))
 
 (defn isprime?-4 [n]
   (let [max (Math/sqrt n)]
 
 (defn primes-generated [a b]
   (take-while isprime?
-              (map #(+ (* % % ) (* a %) b)
+              (map #(abs (+ (* % %) (* a %) b))
                    (range b))))
 
 (defn num-primes-generated [a b]
   (count (primes-generated a b)))
 
 (defn test-quadratic [n]
-  (reduce max-first
-          (for [a (range (- 1 n) n)
-                ;;         b (range (- 1 n) n)
-                b (take-while #(< % n) primes)
-                ]
-            (list (num-primes-generated a b) a b))))
-
-(defn test-quadratic [n]
-  (reduce * (rest
+  (reduce * (next
              (reduce max-first
-                     (for [a (range (- 1 n) n)
-                           ;;         b (range (- 1 n) n)
-                           b (take-while #(< % n) primes)
-                           ]
-                       (list (num-primes-generated a b) a b))))))
-
-;; (test-quadratic 1000)
+                     (let [b-range (take-while #(< % n) primes)]
+                       (for [a (range (- 1 n) n)
+                             b b-range
+                             ]
+                       (list
+                        (num-primes-generated a b)
+                        a b)))))))
+
+;; (time (test-quadratic 1000))
+;; "Elapsed time: 2716.664 msecs"
 ;; -59231
 
 ;}}}
 ;; Find the sum of all the numbers that can be written as the sum of
 ;; fifth powers of their digits.
 
-
-
 ;; 6*9^5 = 354294 < 999999 so they must be less than 354294
 (defn fourth-power? [n]
   (= n (reduce + (map #(* % % % %) (to-digits n)))))
 (defn fifth-power? [n]
   (= n (reduce + (map #(* % % % % %) (to-digits n)))))
 
-;; (reduce + (filter fourth-power? (range 2 354294)))
+;; (time (reduce + (filter fourth-power? (range 2 354294))))
+;; "Elapsed time: 3339.717 msecs"
 ;; 19316
 
-;; (reduce + (filter fifth-power? (range 2 354294)))
+;; (time (reduce + (filter fifth-power? (range 2 354294))))
+;; "Elapsed time: 3429.407 msecs"
 ;; 443839
 
 ;}}}
                                          y (range x 10000)]
                                      (list (* x y) x y)))))))
 
+;; (time (pandigital-9-product))
+;; "Elapsed time: 23457.702 msecs"
+;; 45228
+
 ;}}}
 ;{{{ problem 33 -- weird cancelling fractions
 
 (defn sum-of-factorials? [n]
   (= n (reduce + (map factorial (to-digits n)))))
 
-;; (reduce + (filter sum-of-factorials? (range 3 2540160)))
+;; (time (reduce + (filter sum-of-factorials? (range 3 2540160))))
+;; "Elapsed time: 30511.995 msecs"
 ;; 40730
 
 ;}}}
           (filter #(every? isprime? (circulars %))
                   (primes-below n)))))
 
-;; (circular-primes 1000000)
+;; (time (circular-primes 1000000))
+;; "Elapsed time: 5006.545 msecs"
 ;; 55
 
 ;}}}
   (reduce + (filter base-2-palindrome?
                     (filter palindrome? (range n)))))
 
-;; (sum-of-palindromes 1000000)
+;; (time (sum-of-palindromes 1000000))
+;; "Elapsed time: 11648.405 msecs"
 ;; 872187
 
 ;}}}
 (defn truncatable-primes []
   (reduce + (take 11 (filter truncatable-prime? (drop 4 primes)))))
 
-
-;; (truncatable-primes)
+;; (time (truncatable-primes))
+;; "Elapsed time: 2588.425 msecs"
 ;; 748317
 
 ;}}}
                                           max-num (Math/pow 10 max-digits)]
                                       (for [y (range 1 max-num)]
                                         (map #(* y %) (range 1 (inc n)))))))))))
-
-;; (x-pandigital-products 9)
+;; (time (x-pandigital-products 9))
+;; "Elapsed time: 207.523 msecs"
 ;; 932718654
 
 ;}}}
   ([a] a)
   ([a b] (if (< (first a) (first b)) b a)))
 
-
 (defn num-right-triangles [p]
   (reduce + (for [a (range 1 (dec p))
                   b (range 1 a)]
           (map #(list (num-right-triangles %) %)
                (range 3 (inc n)))))
 
-;; (perimeter-with-max-right-triangles 1000)
+;; (time (perimeter-with-max-right-triangles 1000))
+;; "Elapsed time: 129329.595 msecs"
 ;; (8 840)
 
 ;}}}
 
 ;; d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000
 
+;; (def that-irrational-number
+;;      (lazy-cons '.
+;;                 ((fn this[n]
+;;                    (lazy-cat (to-digits n) (this (inc n)))) 1)))
+
 (def that-irrational-number
-     (lazy-cons '.
-                ((fn this[n]
-                   (lazy-cat (to-digits n) (this (inc n)))) 1)))
+     (cons '.
+           (lazy-seq
+             ((fn this[n]
+                (concat (to-digits n)
+                        (lazy-seq (this (inc n)))))
+              1))))
 
 (defn product-of-10powers [n]
   (take n (map #(nth that-irrational-number %)
                (iterate #(* 10 %) 10))))
 
+;; (defn product-of-10powers-2 [n]
+;;   (reduce * (take n (map #(nth (lazy-cons '. ((fn this[n]
+;;                                                 (lazy-cat (to-digits n) (this (inc n)))) 1))
+;;                                %)
+;;                          (iterate #(* 10 %) 1)))))
+
 (defn product-of-10powers-2 [n]
-  (reduce * (take n (map #(nth (lazy-cons '. ((fn this[n]
-                                                (lazy-cat (to-digits n) (this (inc n)))) 1))
+  (reduce * (take n (map #(nth (cons '.
+                                     (lazy-seq
+                                       ((fn this[n]
+                                          (concat (to-digits n)
+                                                  (lazy-seq (this (inc n)))))
+                                        1)))
                                %)
                          (iterate #(* 10 %) 1)))))
 
-;; (product-of-10powers 7)
-;; (1 1 5 3 7 2 1)
-
-;; (take n  (iterate #(* 10 %) 1))
+;; (time (product-of-10powers-2 7))
+;; "Elapsed time: 1318.285 msecs"
+;; 210
 
 ;}}}
 ;{{{ problem 41 -- pandigital primes
 (defn largest-pandigital-prime-2 []
   (reduce max (filter isprime? pandigitals)))
 
-;; (largest-pandigital-prime-2)
+;; (time (largest-pandigital-prime-2))
+;; "Elapsed time: 20029.519 msecs"
 ;; 7652413
 
 ;}}}
                  (map word2num
                       (re-seq #"\w+" (slurp file))))))
 
-;; (triangle-words "words.txt")
+;; (time (triangle-words "words.txt"))
+;; "Elapsed time: 34.175 msecs"
 ;; 162
 
 ;}}}
 
 (defn prime-list-to-stuff [prime-lists accum]
   ;; I need to do something special when prime-list2 is empty
-  (if (nil? prime-lists)
+  (if (not (seq prime-lists))
     (make-pandigital accum)
 
     (let [prime-list (first prime-lists)]
 ;; Actually I could do all this with no lists, just numbers, rem and a
 ;; multiplier (though some things would be harder)
 
-;; (pandigital-substring)
+;; (time (pandigital-substring-3 4888))
+;; "Elapsed time: 56.964 msecs"
 ;; 16695334890
 
 ;}}}
   (* 1/2 n (dec (* 3 n))))
 
 (def pentagonal-numbers
-     ((fn this[n]
-       (lazy-cons (nth-pentagonal n)
-                  (this (inc n))))
-      1))
+     (lazy-seq
+       ((fn this[n]
+          (cons (nth-pentagonal n)
+                (lazy-seq (this (inc n)))))
+        1)))
 
 (defn pentagonal? [P]
   (let [D   (+ 1 (* 24 P))
               ]
           (list (- P1 P2) P2 P1 (+ P1 P2)))))
 
-;; (find-pentagonal-numbers 1)
-;;
 ;; (time (find-pentagonal-numbers-3 1))
-;; "Elapsed time: 1035.227 msecs"
+;; "Elapsed time: 2.267 msecs"
 ;; ((5482660 1560090 7042750 8602840))
 
 ;}}}
 ;; sum of a prime and twice a square?
 
 (def odd-composites
-     ((fn this [x]
-        (if (isprime? x)
-          (recur (+ 2 x))
-          (lazy-cons x (this (+ 2 x)))))
-      9))
+     (lazy-seq ((fn this [x]
+                  (if (isprime? x)
+                    (recur (+ 2 x))
+                    (cons x (lazy-seq (this (+ 2 x))))))
+                9)))
 
 ;; This could be simpler
 (defn is-square? [n]
                (primes-below n))))
 
 (defn non-goldbachs [x]
-  (take x (filter (complement prime-plus-2-square?)
+  (take x (filter (complement #(seq (prime-plus-2-square? %)))
                   odd-composites)))
 
-;; (non-goldbachs 1)
+;; (time (non-goldbachs 1))
+;; "Elapsed time: 0.161 msecs"
 ;; (5777)
 
 ;}}}
 ;; Find the first four consecutive integers to have four distinct
 ;; primes factors.  What is the first of these numbers?
 
+;; (def integer-quads
+;;      ((fn this[num]
+;;         (lazy-cons (range num (+ 4 num))
+;;                    (this (inc num))))
+;;       1))
+
 (def integer-quads
      ((fn this[num]
-        (lazy-cons (range num (+ 4 num))
-                   (this (inc num))))
+        (cons (range num (+ 4 num))
+              (lazy-seq (this (inc num)))))
       1))
 
 (defn distinct-prime-factors [n]
   (ffirst
-        (filter #(every? (fn [x] (= n (count (distinct (factors x)))))
-                         %)
-                integer-quads)))
-
-;; (distinct-prime-factors 4)
+   (filter #(every? (fn [x] (= n (count (distinct (factors x)))))
+                    %)
+           integer-quads)))
+
+;; (time (distinct-prime-factors 4))
+;; "Elapsed time: 1790.427 msecs"
 ;; 134043
 
 ;}}}
 ;; What 12-digit number do you form by concatenating the three terms
 ;; in this sequence?
 
+(defn rrest [seq]
+  (rest (rest seq)))
+(defn frrest [seq]
+  (first (rest (rest seq))))
+
 (defn arithmetic-prime-seq []
   (filter #(and (isprime? (first (rrest %)))
                 (< (first (rrest %)) 10000)
                     p3 (+ p2 d)]
                 (list p1 p2 p3))))))
 
-;; (arithmetic-prime-seq)
+;; (time (arithmetic-prime-seq))
+;; "Elapsed time: 2.644 msecs"
 ;; ((1487 4817 8147) (2969 6299 9629))
 
 ;}}}
                            (list x (reduce + (take x seq))))
                          accum))))))
 
+(defn frfirst [seq]
+  (first (rest (first seq))))
+
 (defn consecutive-prime-sums-below [n]
-  (first (rfirst (consecutive-prime-sums-below-helper (primes-below n) n nil))))
+  (frfirst (consecutive-prime-sums-below-helper (primes-below n) n nil)))
 
 ;; (time (consecutive-prime-sums-below 1000000))
-;; "Elapsed time: 537056.241 msecs"
+;; "Elapsed time: 421993.041 msecs"
 ;; 997651
 
 ;}}}
 ;; 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)))
-
+     (cons 1
+           ((fn this[cur amt]
+              (let [new-seq (map #(+ cur (* amt %)) (range 1 5))]
+                (concat (map #(+ cur (* amt %)) (range 1 5))
+                        (lazy-seq (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)))
 (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)))
+     (cons '(1)
+           ((fn this[cur amt]
+              (let [new-seq (map #(+ cur (* amt %)) (range 1 5))]
+                (cons (map #(+ cur (* amt %)) (range 1 5))
+                      (lazy-seq (this (nth new-seq 3) (+ 2 amt))))))
+            1 2)))
 
 (defn bob [n]
   (take n
              (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))))
          (recur (rest diags) cur-primes cur-cnt cur-len))))
    (drop 1 spiral-diagonals) 0 1 1))
 
-;; (find-spiral-prime-ratio 1/10)
+;; (time (find-spiral-prime-ratio 1/10))
+;; "Elapsed time: 5979.02 msecs"
 ;; 26241
 
 ;}}}
     (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)))))
+  (lazy-seq
+    (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))]
                           key (find-key stream)]
                       (map #(char (bit-xor key %)) stream)))))))
 
-;; (reduce + (map int (decipher-xor "cipher1.txt" 3)))
+;; (time (reduce + (map int (decipher-xor "cipher1.txt" 3))))
+;; "Elapsed time: 46.001 msecs"
 ;; 107359
 
 ;}}}
          (recur new-map (rest seq)))))
    {} seq))
 
-;; (smallest-permutable 5 cubes)
+;; (time (smallest-permutable 5 cubes))
+;; "Elapsed time: 294.208 msecs"
 ;; 127035954683
 
 ;}}}
 ;; 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)))
+     (cons 2
+           ((fn this[n]
+              (concat (list 1 n 1)
+                      (lazy-seq (this (+ 2 n)))))
+            2)))
+
+(defn continued-fraction-nth-convergent [s limit]
+  (/ ((fn this[s accum]
+        (if (seq s)
+           (recur (next s) (/ (+ (first s) accum)))
           accum))
-      (reverse (take limit seq)) 0)))
+      (reverse (take limit s)) 0)))
 
 (defn nth-e-convergent [n]
   (sum-of-digits (. (continued-fraction-nth-convergent continued-fraction-e n) numerator)))
     (range (inc n))))
 
 ;; (time (minimal-diaphontine-x 100))
-;; "Elapsed time: 256626.027 msecs"
-;; "Elapsed time:  45649.972 msecs"
-;; 61
-
 
 ;}}}
 ;{{{ problem 67 -- more triangle path maximizing
                                              (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 has-smallest-first? [s]
+  (not (or (not (seq s))
+           (seq (let [firsts (map first s)
+                      ff (first firsts)]
+                  (filter #(> ff %) firsts))))))
 
 (defn permutations-summing [seq]
   (apply concat (for [x seq
                             (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)))))))))
+  (pipeline
+    :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
                       (range 2 (inc n))))))
 
 ;; (time (max-totient-quotient 1000000))
-;; "Elapsed time: 17440.532 msecs"
+;; "Elapsed time: 25152.347 msecs"
+;; "Elapsed time: 25949.301 msecs"
 ;; 510510
-;; (factors 510510)
+;; (factors 510510) (17 13 11 7 5 3 2)
 
 ;}}}
 ;{{{ problem 70 -- permuted totient quotient
 ;;      (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)))))))
+  (pipeline
+    :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"
+;; "Elapsed time: 513006.925 msecs"
 ;; 8319823
 
 ;}}}
       :map #(next-smallest-fraction a b %)
       (range 2 (inc n)))))
 
-;; (next-smallest-fraction-in-range 3/7 1000000)
+;; (time (next-smallest-fraction-in-range 3/7 1000000))
+;; "Elapsed time: 5159.219 msecs"
 ;; 428570/999997
 
 ;}}}
   :map totient
   (range 2 (inc n))))
 
-;; (num-fractions 1000000)
+;; (time (num-fractions 1000000))
+;; "Elapsed time: 20946.636 msecs"
 ;; 303963552391
 
 ;}}}
 
 ;}}}
 
+ported to here
 ;{{{ problem 75 -- wire right triangles
 
 ;; It turns out that 12 cm is the smallest length of wire that can be
   (take-while #(<= % max)
               (iterate #(+ % n) n)))
 
-(defn run-length-encode-no-recur [seq]
-  ((fn [seq accum]
-    (if (or (nil? seq)
-            (nil? (first seq)))
+(defn run-length-encode-no-recur [s]
+  ((fn [s accum]
+    (if (or (empty? s)
+            (nil? (first s)))
       (reverse accum)
-      (let [f (first seq)
-            cnt (count-uniq seq)]
-        (recur (drop cnt seq) (list* (list f cnt) accum)))))
-   seq (list)))
+      (let [f (first s)
+            cnt (count-uniq s)]
+        (recur (drop cnt s) (list* (list f cnt) accum)))))
+   s (list)))
 
 (defn pythagorean-triples [n]
-  ;; (count-uniq seq)
   (pipeline
     :count
     :filter #(= 1 (frest %))
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.