Project Euler Problem 6 in Clojure

Wrote a square function so that the result wasn't cast to Double, so I didn't have to mess about with the formatting of the answer.

(defn square [num]
  (* num num))

(defn sum-squares [max]
  (reduce + (map #(square %) (range 1 max))))

(defn square-sum [max]
  (square (apply + (range 1 max))))

(defn solve []
  (- (square-sum 101) (sum-squares 101)))

Project Euler Problem 5 in Clojure

Not very impressive performance, this brute-force method takes about 30 seconds to run. Could probably be a lot quicker if factors were chosen more intelligently.

(def factors (into () (range 20 3 -1)))

(defn- all-factors [number]
  (if (every? #(zero? (mod number %)) factors)
    number
    (recur (inc number))))

(defn solve[]
  (all-factors 1))

Project Euler Problem 4 in Clojure

Most of my time was spent playing with for, trying to work out if it was best to do it all in the list comprehension. In the end I thought it was more readable to pull the creation of the products out into its own function.

(defn palindrome? [str]
  (if (= (first str) (last str))
    (if (<= 2 (count str))
      (recur (rest (butlast str)))
      true)
    false))

(defn three-digit-numbers []
  (range 100 1000))

(defn- products []
  (distinct
    (for [n1 (three-digit-numbers) n2 (three-digit-numbers)]
      (* n1 n2))))

(defn solve []
  (apply max (filter #(palindrome? (str %)) (products))))

Project Euler Problem 3 in Clojure - part 2

So the solution in part 1 was no good - it took half an hour to run. I spent a while trying and failing to make a lazy, purely functional version but after talking to Ed about his solution I came up with this, which runs in about 500msec :

(defn factor? [big small]
  (zero? (mod big small)))

(defn prime? [n]
  (not-any? #(factor? n %) (range 2 n)))

(defn primes []
  (filter #(prime? %) (iterate inc 2)))

(defn prime-factors [n]
  (let [factors (atom ())]
    (last
     (for [candidate (primes) :while (< (apply * @factors) n)]
       (if (factor? n candidate)
      (swap! factors conj candidate))))))

(defn solve []
  (first (prime-factors 600851475143)))

Project Euler Problem 3 in Clojure - part 1

This one is proving a bit tougher. First you need a list of prime numbers. I'm using the Euler's Sieve to produce primes.

First I wrote this function:

(defn sieve-numbers [position numbers]
  (if (>= position (count numbers))
  numbers
    (let [prime (nth numbers position)]
      (let [products (map #(* prime %) numbers)]
        (let [filtered (remove #(some #{%} products) numbers)]
          (recur (inc position) filtered))))))

which worked but was dog-slow:

;; (dotimes [_ 5] (time (sieve-euler 1000)))
;; "Elapsed time: 484.981564 msecs"
;; "Elapsed time: 459.624835 msecs"
;; "Elapsed time: 462.771112 msecs"
;; "Elapsed time: 460.312279 msecs"
;; "Elapsed time: 462.203786 msecs"
;; nil

To solve the problem we need to primes up to ceil(sqrt(N)) which is 775147 so that first method would take days.

To speed up the filtering I rewrote to use a SortedSet:

(defn sieve-numbers [primes candidates]
  (if (empty? candidates)
  primes
  (let [prime (first candidates)]
    (let [products (map #(* prime %) candidates)]
      (let [filtered (difference candidates products #{prime})]
        (recur (conj primes prime) filtered))))))

which is about 32 times faster:

;; (dotimes [_ 5] (time (sieve-euler 1000)))

;; "Elapsed time: 13.061787 msecs"
;; "Elapsed time: 12.994529 msecs"
;; "Elapsed time: 13.716897 msecs"
;; "Elapsed time: 13.237088 msecs"
;; "Elapsed time: 14.33136 msecs"

Still not good enough though. I need a faster sieve before I can even attempt to factor the large(ish) number and solve problem 3 inside a minute. I think my next step will be to pre-filter some of the non-primes with a Wheel Factorisation. This method wont remove all the non-primes, but it might be fun to implement.

I'm leaving the current sieve chugging away tonight to see how long it takes anyway, for comparison.

Project Euler Problem 2 in Clojure

;; lazy fibo stolen from programming clojure p137
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [1 2])))

(defn solve []
(reduce + (filter even? (take-while #(> 4000000 %) (fibo)))))

Project Euler Problem 1 in Clojure

I'm trying to solve Project Euler using Clojure as an exercise to learn the language. My aim is to favour readability over performance, but still execute each problem inside a minute.


(defn is-multiple [number factor]
(zero? (mod number factor)))

(defn is-multiple-3-or-5 [number]
(or (is-multiple number 3)
(is-multiple number 5)))

(defn solve []
(reduce + (filter is-multiple-3-or-5 (range 1 1000))))