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
Pingback: Project Euler in Clojure – Problem 8 « Proctor It
There seems to be a number-theoretical oversight. The generation formula you use does not generate all Pythagorean triplets (e.g. 6, 8, 10) , so there is some luck in that you actually happen to catch the one that fulfills the sum criterion.
The triple [6 8 10] gets generated by the call to pythagorean-triple-for with the values [3 1].
Am I missing something? If there are numbers I am not generating I was, and still am, not seeing it.
Oops. Sorry. [9 12 15] ?
I was in fact missing that. I have an updated solution which accounts for the missing triples as well. The update can be found at the link above for Problem 9 Redux. Thanks for pointing out the missing triples.
–Proctor
All the code in pythagorean-triples could be replaced with a for and use ranges:
(for [n (range 1 1000)
m (range n 1000)]
(pythagorean-triple-for m n))
This problem is small enough to solve by brute force, without being clever about how you generate the triples. Try writing it as a
for
loop (probably with the:let
and:when
options).Pingback: Project Euler in Clojure – Problem 9 Redux « Proctor It