This is my solution to Problem 9 of Project Euler. If you would like to track my progress you can follow my repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  Here is my solution to Problem 8.

Problem 9 of Project Euler is described as:

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

(defn pythagorean-triple-for [m n]
  (let [mm (Math/pow m 2)
        nn (Math/pow n 2)]
        (sort [(int (- mm nn)) (* 2 m n) (int (+ mm nn))])))

(defn pythagorean-triples
  ([] (cons (pythagorean-triple-for 2 1) (pythagorean-triples 2 2)))
  ([m n]
      (if (< n m)
        (lazy-seq (cons (pythagorean-triple-for m n) (pythagorean-triples m (inc n))))
        (recur (inc m) 1))))

(defn problem9 []
   (multiply (first (filter #(= (sum %) 1000) (pythagorean-triples)))))

The function pythagorean-triple-for generates the Pythagorean Triple which corresponds to any pair of digits (m n) where n < m. The Pythagorean Triple for (2 1) is the triple [3 4 5], and for (32 21) results in [53 1344 1465].

The function pythagorean-triples creates a lazy sequence of triples by generating triples starting with m = 2 and n = 1, by incrementing n until m = n, and then increments m, and continues for all values of n from 1 to m. Resulting in calls to pythagorean-triple-for against the following pairs ([2 1] [3 1] [3 2] [4 1] [4 2] [4 3] …).

The function problem9 then finds the first where the sum of the triple is equal to 1000, and takes the multiple of that result. This was solved before Arcane Sentiment posted his comment about the helper functions for sum and multiply. After cleaning up the previously code to use those, the code then became the following.

(defn problem9 []
   (multiply (first (filter #(= (sum %) 1000) (pythagorean-triples)))))

Having played a bit more with Clojure since I solved this, the function pythagorean-triples seems like it could be nicer. The mix of recur, and the recursive function call seem kinda smelly, and looking at the solution again, I am now wondering if there is a use of map or reduce which might clean this up. Any thoughts?

**Update**
Thanks to the comments I have updated the function pythagorean-triples, and posted the changes in the post Problem 9 Redux.

–Proctor

This is my solution to Problem 8 of Project Euler. If you would like to track my progress you can follow my repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  Here is my solution to Problem 7.

Problem 8 of Project Euler is described as:

Find the greatest product of five consecutive digits in the 1000-digit number.
          73167176531330624919225119674426574742355349194934
          96983520312774506326239578318016984801869478851843
          85861560789112949495459501737958331952853208805511
          12540698747158523863050715693290963295227443043557
          66896648950445244523161731856403098711121722383113
          62229893423380308135336276614282806444486645238749
          30358907296290491560440772390713810515859307960866
          70172427121883998797908792274921901699720888093776
          65727333001053367881220235421809751254540594752243
          52584907711670556013604839586446706324415722155397
          53697817977846174064955149290862569321978468622482
          83972241375657056057490261407972968652414535100474
          82166370484403199890008895243450658541227588666881
          16427171479924442928230863465674813919123162824586
          17866458359124566529476545682848912883142607690042
          24219022671055626321111109370544217506941658960408
          07198403850962455444362981230987879927244284909188
          84580156166097919133875499200524063689912560717606
          05886116467109405077541002256983155200055935729725
          71636269561882670428252483600823257530420752963450

(defn digits-of [n]
  (map #(Integer/parseInt (str %)) (str n)))

(defn problem8 []
  (let [n 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450]
    (apply max (map
                 #(apply * %) (partition 5 1 (digits-of n))))))

The digits-of function takes a number and creates a sequence of the digits of the number, in the same way a string can be treated as a sequence of characters. I then call partition on that stream of digits to get the digits in groups of five. Those groups of five get multiplied together, and we find the max of those results.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
I have posted my solution to Problem 9.

–Proctor

Working through the Project Euler problems, and with the comment from Arcane Sentiment about filtering based off of a set of primes, I was trying to program the Sieve of Eratosthenes. I also realized that the Sieve becomes a set based problem, so I went about trying to solve it using sets.

My first approach was simply using the difference function given in clojure.set.

(defn primes-under [n]
  (loop [sieve (set (cons 2 (range 3 n 2)))
         f 3]
    (if (> (square f) n)
      sieve
      (recur (difference sieve (range (square f) n f)) (inc f)))))

I start with the set of numbers starting by cons-ing 2 onto the range from 3 to n, skiping every other number, to get the odd numbers up to n.

The new sieve becomes the the difference between the current sieve, and the multiples of the factor f. I use (range (square f) n f) as a subset of the factors of f up to the number n. I start the range at the square of the factor, as any multiples below the square of the factor would already have been sieved out from the factors below it. So for multiples of 5, I can ignore (10, 15, 20) as they are multiples of 2 and 3, the other primes below 5, and as a result I only need to get multiples of 5 starting at 25.

When timing this solution by using:

(time (dorun (primes-under 1000000)))

The timing for the primes under 1,000,000 is around 2.1 seconds, and anywhere from 6 to 10 seconds for the primes under 2,000,000.

I wasn’t happy with this performance, especially after seeing Christophe Grand’s solution and timing on his blog post Everybody loves the Sieve of Eratosthenes.

I decided to try my hand at solving this using a transient set. After many missteps in using a transient set, due to not having used them before, I came up with the following solution:

(defn primes-under2 [n]
  (let [sieve (transient (set (cons 2 (range 3 n 2))))]
    (loop [s sieve
           f 3]
      (cond (> (square f) n) (persistent! s)
            :else (recur (reduce disj! s (range (square f) n f)) (inc f))))))

I define sieve as a transient set, and instead of using difference, I call reduce on the sieve using the function disj! for the ranges of numbers to filter out. I need to use disj! to remove that number from the sieve, as this is now a transient set I am working against.

The timing of this solution is now down to 1.1 seconds for primes under 1,000,000, and primarily in the 3 second range for the primes under 2,000,000.

I am still not quite satisfied with this solution, and would love suggestions as to how to avoid those numbers which have been filtered out of the sieve already.  As I just do a (inc f), I would still get the numbers 4, 6, 8, 9, 25, etc, that are multiples of other primes, but I could not figure out how to skip these numbers.  I tried the functions contains?, get, superset?, subset?, difference, but these were not giving me the result when dealing with the transient set.

If someone could tell me if I have missed anything I should try for filtering out non-prime numbers as factors, I would love to get your suggestions to try it out, and I will post a follow up with the results.

–Proctor

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 6 can be found here.

Problem 7 of Project Euler is described as:

What is the 10 001st prime number?

(defn is-prime? [n]
  (cond (<= n 1) false
        (= n 2) true
        :else (loop [f 2]
                (cond (zero? (rem n f)) false
                      (> f (Math/sqrt n)) true
                      :else (recur (inc f))))))

(defn problem7
  ([] (problem7 10001))
  ([n] (first (skip-n (dec n) (filter is-prime? (iterate inc 1))))))

The is-prime? function check to see if the number is prime by checking if any of the numbers from 2 to the square root of the number is a divisor of the number.

The problem7 function is finds the n-th number in the sequence by skiping n-1 items, and then taking the first item of that sequence. This was before a previous post in which someone pointed out that the drop function was available instead of my home rolled skip-n function, so that can be replaced on the update.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 8 has been posted.

–Proctor

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 5 can be found here.

Problem 6 of Project Euler is described as:

Find the difference between the sum of the squares of the
first one hundred natural numbers and the square of the sum.

This is another problem that seems to translate almost directly from the problem statement into the operations that need to be performed.

I find the square of the sums from 1 to the (inc n), where n is bound to 100 for the problem definition, as I want the number that n is bound to to be included in the range. This is coded as:

(Math/pow (reduce + (range 1 (inc n))) 2)

As well as I find the sum of the squares from 1 to the (inc n).

(reduce + (map #(Math/pow % 2) (range 1 (inc n))))

I then pieced these two solutions together, subtracting the two values. When doing this at the REPL, it gave the result as an exponent, which I didn’t like the look of, so I put the function bigint around the subtraction function, giving the full solution as:

(defn problem6
  ([] (problem6 100))
  ([n] (bigint (-
         (Math/pow (reduce + (range 1 (inc n))) 2)
         (reduce + (map #(Math/pow % 2) (range 1 (inc n))))))))

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 7 can be found here.

–Proctor

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 4 can be found here.

Problem 5 of Project Euler is described as:

What is the smallest positive number that is evenly
divisible by all of the numbers from 1 to 20?

In reading this problem I realized that this is just another way to state:

Find the Least Common Multiple of all of the numbers between 1 and 20.

The solution I came up with is:

(ns project-euler.core
  (:require [clojure.string :as string]
            clojure.math.numeric-tower))

(defn problem5
  ([] (problem5 20))
  ([n] (reduce lcm 1 (range 2 (inc n)))))

I found that previous to Clojure 1.2 there was a math library in Clojure-Contrib, which after 1.2 is now been moved to clojure.math.numeric-tower, so that now gets included in the vector of libraries in the :require of the ns function.

Once I had this, it was now just as simple as calling the reduce function with the function lcm, feeding it a initialization value of 1 to the reduce function and having that operate on the range of numbers from 2 to the number bound to the var n, which when called without parameters will use the value of twenty as specified in the problem definition. By defining the different arities for the function problem5, it allowed me to call the function with different numbers to the results of the function, as the full description gave the solution for the numbers in the range of 1 through 10.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 6 has been posted here.

–Proctor

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 3 can be found here.

Problem 4 of Project Euler is described as:

Find the largest palindrome made from the product of two 3-digit numbers.

The solution I came up with is:

(ns project-euler.core
  (:require [clojure.string :as string]))

(defn is-palindrome? [s]
 (= (str s) (string/join (reverse (str s)))))

(defn problem4 []
 (apply max (filter is-palindrome? (for [x (range 100 1000) y (range 100 1000)] (* x y)))))

As I want to use the join function in the clojure.string namespace, I added the :require keyword and aliased clojure.string as string using the :as keyword from the namespace macro.

The function is-palindrome? converts the value into a string, reverses the stream of characters in the string and then joins them back together and then compares it with the value as a string.

As defined problem4 does the meat of the work, by using a for loop over the set of of values from 100 to 999 for the binding of x and y, and multiplies x and y for each combination. This set is then filtered against the is-palindrome function, and the filtered sequence is then passed to the max function via apply.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 5 has been posted here.

–Proctor

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 2 can be found here.

Problem 3 of Project Euler is described as:

What is the largest prime factor of the number 600851475143 ?

For this problem, I needed to generate the prime factors of a number. In order to generate the prime factors, I decided to pul out the Uncle Bob’s (found here, here, here, and here) Prime Factors Kata and apply it to Clojure. By doing this kata, I test drove the result, and decided I would give Brian Marick’s Midje a shot and play with that some as well. The resulting tests are as follows.

(ns project-euler.prime-factors-test
  (:use clojure.test
        midje.sweet
        project-euler.core))

(defn mersenne [n]
  (int (dec (Math/pow 2 n))))

(fact
  (prime-factors-of 1) => []
  (prime-factors-of 2) => [2]
  (prime-factors-of 3) => [3]
  (prime-factors-of 4) => [2 2]
  (prime-factors-of 5) => [5]
  (prime-factors-of 6) => [2 3]
  (prime-factors-of 7) => [7]
  (prime-factors-of 8) => [2 2 2]
  (prime-factors-of 9) => [3 3]
  (prime-factors-of 10) => [2 5]
  (prime-factors-of 11) => [11]
  (prime-factors-of 12) => [2 2 3]
  (prime-factors-of 16) => [2 2 2 2]
  (prime-factors-of 25) => [5 5]
  (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37]
  (prime-factors-of (mersenne 17)) => [(mersenne 17)])

The total solution to problem 3 is as follows, with the test driven function for generating the prime factors, is:

(defn factors-starting-at [f n]
  (cond (= n 1) []
        (zero? (rem n f)) (cons f (factors-starting-at f (/ n f)))
        :else (recur (inc f) n)))

(defn prime-factors-of [n]
  (factors-starting-at 2 n))

(defn problem3 []
  (reduce max (prime-factors-of 600851475143)))

The resulting function for prime-factors-of calls the recursive function factors-starting-at with the first factor of 2, and the number itself. The factors-starting-at returns an empty vector when n is one. When the factor is actually a factor of the number (zero? (rem n f)) the returned result is the factor cons’ed onto the result of calling factors-starting-at again with the same factor, and the number divided by that factor. Otherwise, we return the result of recur-ing with the same number and the factor incremented again.

The solution to problem 3 is actually very simple in Clojure after one generates the prime factors for a number. All that one has to do is reduce the sequence of prime factors with the function max to find the largest prime factor for the number 600851475143.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 4 in Clojure.

–Proctor

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 1 can be found here.

Problem 2 of Project Euler is described as:

By considering the terms in the Fibonacci sequence whose values do
not exceed four million, find the sum of the even-valued terms.

The solution I came up with is:

(defn skip-n [n s]
  (cond
    (<= n 0) s
    :else (recur (dec n) (rest s))))

(defn fib
  ([] (concat [0N 1N] (fib 0N 1N)))
  ([a b] (let [c (+ a b)]
          (lazy-seq
            (cons c (fib b c))))))

(defn problem2 []
  (reduce + (filter #(even? %) (take-while #(< % 4000000N) (skip-n 2 (fib))))))

As a didn’t see a skip function, which would keep a sequence, but skip over a given number of inputs, I created the function skip-n. The skip function calls the function rest on the sequence n number of times by using recur, and decrementing n.

The function fib generates the Fibonacci sequence lazily by using the function lazy-seq to create a lazily evaluated sequence, as I want the numbers generated until the time that I decide I do not need them anymore. Instead of trying to determine how many that will be before I generate them, I just decided to make them generated lazily.

The previous two functions were a helper function, and the function to generate the Fibonacci sequence (huh, sequence is even in the name). The work to determine the results of the problem are found in the function problem2. This function uses the skip-n function to skip the first two results, as Project Euler shows the Fibonacci sequence starting as 1, 2, 3, … instead of the starting as 0, 1, 1, 2, 3, … so I skip the first two in the sequence. I then use the take-while function to take only those items which are less than 4 million, which I then feed to the filter function to take only those items from the Fibonacci sequence that are even. The last step is to use the reduce function to sum all of those items together to get the final result.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 3 in Clojure.

–Proctor