# Archive for category Project Euler

### Clojure function has-factors-in?

Posted by Proctor in Clojure, Declarative Programming, Deliberate Practice, Functional Programming, Lisp, Project Euler, Refactoring on August 27, 2012

Just another quick post this evening to share a new function I created as part of cleaning up my solution to Problem 1 of Project Euler.

Was just responding to a comment on Google+ on my update sharing the post Project Euler in Clojure – Problem 16, and I saw the commenter had his own solution to problem 1. In sharing my solution I realized that I could clean up my results even further, and added a function `has-factors-in?`

. These updates have also been pushed to my Project Euler in Clojure Github repository for those interested.

(defn has-factors-in? [n coll] (some #(factor-of? % n) coll))

Where before I had:

(defn problem1 ([] (problem1 1000)) ([n] (sum (filter #(or (factor-of? 3 %) (factor-of? 5 %))) (range n))))

It now becomes:

(defn problem1 ([] (problem1 1000)) ([n] (sum (filter #(has-factors-in? % [3 5]) (range n)))))

This change makes my solution read even more like the problem statement given.

Your thoughts?

–Proctor

### Project Euler in Clojure – Problem 16

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on August 22, 2012

Here is my solution to Problem 16 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 16 of Project Euler is:

What is the sum of the digits of the number 2^1000

This problem was straight forward since I already had the function `digits-of`

defined from problem8. I was able to be very declarative in my problem, so much so, that it reads as the problem statement you are asked to solve.

(defn problem16 ([] (problem16 1000)) ([n] (sum (digits-of (expt 2 n)))))

As always, any feedback you have for me is greatly appreciated.

–Proctor

### Project Euler in Clojure – Problem 15

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on August 16, 2012

Here is my solution to Problem 15 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 15 of Project Euler is to find the starting number with the longest Collatz sequence, summarized from the problem page as:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 2020 grid?

I started this problem, by trying to tracing and counting the routes through grids of 2×2, 3×3, and 4×4, and even setled in and did a 5×5 square. Having these numbers, and knowing I had two choices for ever position I was in, except for when the path got to the far edge and bottom, I had a hint at the growth rate of the problem. I tried some powers of 2 with the relationship of the numbers, and some factorials with the numbers. After seeing some possible relationships with the factorials that might be leading me in the right direction, I tried a number of permutation calculations, and the combination calculations. Having seen the numbers show up in different combination results, I then spent time back-calculating from those numbers into my `n`

s, and found that the pattern seemed to match 2n Choose n.

The source code to this was the `factorial`

function:

(defn factorial [n] (multiply (range 1M (inc (bigdec n)))))

And, I could have done it recursively, but I figured I would just operate against the sequence of numbers, especially now that the reducers are available in the Clojure 1.5-Alpha 3 release (at the time of this writing) of Clojure. After I get through a few more problems (of which I am working ahead of these posts), I am thinking it would be interesting to run the same Project Euler Problems against 1.4 and 1.5 using the reducers library, just substituting map/reduce for the reduce/combine functionality, and seeing how much effort it takes to move them over, as well as the differences in the timings of the different problems.

The other base function I needed was a `combination`

function:

(defn combination [n k] (cond (zero? n) 0 (zero? k) 1 :else (/ (factorial n) (* (factorial (- n k)) (factorial k)))))

This function just does the basic calculation for combinations, from the formula:

With that, and my stumbling upon the matching of the fact that is the solution to ne number of paths through the square the function `problem15`

is defined as:

(defn problem15 ([] (problem15 20)) ([n] (combination (+ n n) n)))

As always, any feedback you have for me is greatly appreciated.

–Proctor

### Project Euler in Clojure – Problem 14

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 23, 2012

Here is my solution to Problem 14 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 14 of Project Euler is to find the starting number with the longest Collatz sequence, summarized from the problem page as:

The following iterative sequence is defined for the set of positive integers: n -> n/2 (n is even) n -> 3n + 1 (n is odd) [...] Which starting number, under one million, produces the longest chain?

The first function I needed was a function to get the next number in the Collatz sequence.

(defn next-collatz [n] (cond (<= n 1) nil (even? n) (/ n 2) (odd? n) (+ (* 3 n) 1)))

This function mimics the above definition of the sequence, with the distinction of the check to see if the number is less than, or equal to, 1. While not strictly necessary, when I was generating numbers from the REPL, I noticed that the sequence never really terminates, but ends in a repeating sequence of `4 -> 2 -> 1 -> 4 -> 2 -> 1 ->...`

. This can be seen by running the following at the REPL.

(take 15 (iterate next-collatz 8))

Wich results in the sequence `(8 4 2 1 4 2 1 4 2 1 4 2 1 4 2)`

. I used the condition `(<= n 1)`

as a guard condition to as a way to be able to terminate the sequence and make it finite. This could probably be removed at this point, as I did not even use the `nil`

return as a check, except that it would serve as a reminder of the function when playing at the REPL.

The next function I defined was a function to get the count of the numbers in the sequence. I defined it this way in the hopes of trying to memoize the values, but I kept getting an OutOfMemoryException when I tried to use it so I took the memoization away.

(defn collatz-count-for [n] {:pre [(pos? n)]} (if (= n 1) 1 (inc (collatz-count-for (next-collatz n)))))

In this function, I decided I would add a precondition to the function requiring that the parameter to the function be positive. This way I could avoid having to try and generate a Collatz sequence for negative numbers, as they are outside the scope of this problem. The function first checks if the number to generate the sequence for is 1, and if so, the count of the sequence returns 1. For all other positive numbers, we get the length of the sequence for the next Collatz number in the sequence, and increment that value, and return that as the Collatz count.

As I was writing this up, I decided I would take another stab at this, and did some searching to try and find a way to change the memory allocation for the project in the REPL. I found the following post How to Set JVM Memory for Clojure REPL in Emacs, and added the following to my project.clj file.

:jvm-opts ["-Xmx768M"]

When I ran with the following memoized version of the `collatz-count-for`

, it now runs much quicker than it did before. Previously it was a rough mental counting of about 10-15 seconds, and now the first time is runs was 2-3 seconds, and sub second on runs after that even.

(def collatz-count-for (memoize (fn [n] {:pre [(pos? n)]} (if (= n 1) 1 (inc (collatz-count-for (next-collatz n)))))))

The changes needed to memoize the function `collatz-count-for`

is that the `defn`

is now a `def`

, which assigns the identifier of `collatz-count-for`

to the result of passing a now nameless function, with the previous function body, to the function `memoize`

. This allows the function body to remain the same, and only the declaration of the function has to now change.

With those pieces to the problem in place, we can now find the number that generates the longest Collatz sequence.

(defn problem14 ([] (problem14 1000000)) ([n] (first (reduce (fn [memo x] (if (> (second x) (second memo)) x memo)) (map #(vector % (collatz-count-for %)) (range 1 (inc n)))))))

I started by mapping over the numbers from 1 to 1000000, to create vectors representing the pair of the number and the sequence length for that number. An example of which results in the following sequence (shown to the first 10 numbers):

([1 1] [2 2] [3 8] [4 3] [5 6] [6 9] [7 17] [8 4] [9 20] [10 7] ...)

I then feed that sequence into `reduce`

, with a function to find the pair with the largest sequence length by calling `second`

on the vector, resulting in the pair of number and sequence length with the largest sequence length. And having found that vector, I use first to find what the number with the largest sequence length is.

This seems like it might be generic enough (idiomatic pattern) that I was missing something that was already defined to do the map and reduce on a structure like this, but I could not find anything. If anybody knows of anything I would love to see how that might be made more expressive.

–Proctor

### Project Euler in Clojure – Problem 13

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 15, 2012

Here is my solution to Problem 13 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 13 of Project Euler is described as:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. [...]

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:

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

(defn problem13 [] (let [numbers [37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 44274228917432520321923589422876796487670272189318 47451445736001306439091167216856844588711603153276 70386486105843025439939619828917593665686757934951 62176457141856560629502157223196586755079324193331 64906352462741904929101432445813822663347944758178 92575867718337217661963751590579239728245598838407 58203565325359399008402633568948830189458628227828 80181199384826282014278194139940567587151170094390 35398664372827112653829987240784473053190104293586 86515506006295864861532075273371959191420517255829 71693888707715466499115593487603532921714970056938 54370070576826684624621495650076471787294438377604 53282654108756828443191190634694037855217779295145 36123272525000296071075082563815656710885258350721 45876576172410976447339110607218265236877223636045 17423706905851860660448207621209813287860733969412 81142660418086830619328460811191061556940512689692 51934325451728388641918047049293215058642563049483 62467221648435076201727918039944693004732956340691 15732444386908125794514089057706229429197107928209 55037687525678773091862540744969844508330393682126 18336384825330154686196124348767681297534375946515 80386287592878490201521685554828717201219257766954 78182833757993103614740356856449095527097864797581 16726320100436897842553539920931837441497806860984 48403098129077791799088218795327364475675590848030 87086987551392711854517078544161852424320693150332 59959406895756536782107074926966537676326235447210 69793950679652694742597709739166693763042633987085 41052684708299085211399427365734116182760315001271 65378607361501080857009149939512557028198746004375 35829035317434717326932123578154982629742552737307 94953759765105305946966067683156574377167401875275 88902802571733229619176668713819931811048770190271 25267680276078003013678680992525463401061632866526 36270218540497705585629946580636237993140746255962 24074486908231174977792365466257246923322810917141 91430288197103288597806669760892938638285025333403 34413065578016127815921815005561868836468420090470 23053081172816430487623791969842487255036638784583 11487696932154902810424020138335124462181441773470 63783299490636259666498587618221225225512486764533 67720186971698544312419572409913959008952310058822 95548255300263520781532296796249481641953868218774 76085327132285723110424803456124867697064507995236 37774242535411291684276865538926205024910326572967 23701913275725675285653248258265463092207058596522 29798860272258331913126375147341994889534765745501 18495701454879288984856827726077713721403798879715 38298203783031473527721580348144513491373226651381 34829543829199918180278916522431027392251122869539 40957953066405232632538044100059654939159879593635 29746152185502371307642255121183693803580388584903 41698116222072977186158236678424689157993532961922 62467957194401269043877107275048102390895523597457 23189706772547915061505504953922979530901129967519 86188088225875314529584099251203829009407770775672 11306739708304724483816533873502340845647058077308 82959174767140363198008187129011875491310547126581 97623331044818386269515456334926366572897563400500 42846280183517070527831839425882145521227251250327 55121603546981200581762165212827652751691296897789 32238195734329339946437501907836945765883352399886 75506164965184775180738168837861091527357929701337 62177842752192623401942399639168044983993173312731 32924185707147349566916674687634660915035914677504 99518671430235219628894890102423325116913619626622 73267460800591547471830798392868535206946944540724 76841822524674417161514036427982273348055556214818 97142617910342598647204516893989422179826088076852 87783646182799346313767754307809363333018982642090 10848802521674670883215120185883543223812876952786 71329612474782464538636993009049310363619763878039 62184073572399794223406235393808339651327408011116 66627891981488087797941876876144230030984490851411 60661826293682836764744779239180335110989069790714 85786944089552990653640447425576083659976645795096 66024396409905389607120198219976047599490197230297 64913982680032973156037120041377903785566085089252 16730939319872750275468906903707539413042652315011 94809377245048795150954100921645863754710598436791 78639167021187492431995700641917969777599028300699 15368713711936614952811305876380278410754449733078 40789923115535562561142322423255033685442488917353 44889911501440648020369068063960672322193204149535 41503128880339536053299340368006977710650566631954 81234880673210146739058568557934581403627822703280 82616570773948327592232845941706525094512325230608 22918802058777319719839450180888072429661980811197 77158542502016545090413245809786882778948721859617 72107838435069186155435662884062257473692284509516 20849603980134001723930671666823555245252804609722 53503534226472524250874054075591789781264330331690]] (bigint (reduce str "" (take 10 (digits-of (sum numbers)))))))

Problem 13 was pretty straight-forward, as the problem, I took the list of the one-hundred numbers as a vector, and then called the function sum which has been used in a number of previous problems as well as the digits-of function which was created in my solution to Problem 8. With these two functions, to get the first 10 digits of the sum was to just call `take`

on the result of calling `digits-of`

on the `sum`

of the numbers in the vector `numbers`

.

The rest of the function is to make the output to the REPL nice. I take the individual digits and turn them into a string using `reduce str ""`

, and then call the function `bigint`

to cast it to an integer value.

**Update**

I have posted my solution to Problem 14.

–Proctor

### Project Euler in Clojure – Problem 12

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 9, 2012

This is my solution to Problem 12 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 12 of Project Euler is described as:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. [...] What is the value of the first triangle number to have over five hundred divisors?

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:

(defn factors-starting-at [f n] (cond (= n 1) [] (factor-of? f n) (cons f (factors-starting-at f (/ n f))) :else (recur (inc f) n))) (defn prime-factors-of [n] (factors-starting-at 2 n)) (defn factors-count [n] (multiply (map #(inc %) (vals (frequencies (prime-factors-of n)))))) (defn triangle-numbers ([] (concat [1] (triangle-numbers 1 2))) ([s n] (let [t (+ s n)] (lazy-seq (cons t (triangle-numbers t (inc n))))))) (defn problem12 [] (first (drop-while #(<= (factors-count %) 500) (triangle-numbers))))

The functions `factors-starting-at`

and `prime-factors-of`

get the prime factors of a given number. The function `factors-count`

calls `frequencies`

on the sequence returned by `prime-factors-of`

, and then increments each item in the sequence and multiplies the items together, to get the total number of factors for a number. I found this formula for getting the count of the factors from StackOverflow question: Algorithm to calculate the number of divisors of a given number.

The function `triangle-numbers`

gets a lazy sequence of the triangle numbers, by taking the previous triangle number, and adding the index of the current triangle number.

The function `problem12`

then drops the items in the sequence while the result of `factors-count`

is <= 500, and gets the first triangle number, which is the first number with a the count of the number of factors greater than 500.

–Proctor

### Project Euler in Clojure – Problem 11

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 8, 2012

This is my solution to Problem 11 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 11 of Project Euler is described as:

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?

I looked into using Incanter but didn’t get it setup as I am using Clojure 1.4, and had some issues getting the dependencies resolved. No big deal though, as I just used a vector of vectors to represent a matrix. I created a new file matrix.clj, which got the namespace definition for project-euler.matrix.

(ns project-euler.matrix)

The first function I defined was `transpose`

, since I am going to want to work against the columns, but rows are easier to think about and work with.

(defn transpose [m] (vec (apply map vector m)))

Since I am going to need to find groups of four numbers in the matrix, I defined the following to functions to get all possible groups of four in the rows, and in the columns.

(defn partition-rows [m n step] (if (= (count m) 0) [] (concat (partition n step (first m)) (partition-rows (rest m) n step)))) (defn partition-columns [m n step] (partition-rows (transpose m) n step))

The `partition-rows`

function just concats the results of calling partition on each row with the group size, `n`

, and the step, by calling partition on the first row of the matrix `(first m)`

, and then calling `partition-rows`

again with the remaining rows in the matrix given `(rest m)`

. The function `partition-columns`

simply transposes the matrix `m`

and then calls `partition-rows`

with that matrix.

The next two functions are two helper functions, which were defined after writing some of the following functions, and exist to better express intent.

(defn matrix-get [m r c] (nth (nth m r) c)) (defn row [m n] (nth m n))

The function `matrix-get`

gets the `r`

th row from the matrix `m`

and then gets the `c`

th item in that row. The function `row`

gets the row for a matrix. Again nothing special about these functions except that they help to communicate the intent, and give the concept a name. These were littered around the code so the functions were created as part of tidying up. In looking at it as I was writing up this post, I realized I still didn’t pull out the concept of row in the function `matrix-get`

, and the two functions should probably be defined as follows instead:

(defn row [m n] (nth m n)) (defn matrix-get [m r c] (nth (row m r) c))

Working through getting the diagonals, I posted a call for help about a clean way to get the diagonals for a matrix in the post Smelly matrix diagonals. I got some good comments, and after taking a bit to pick apart the functions, I went with the following from the comments, thanks to Mark.

(defn diagonals [m] (let [rdim (count m) cdim (count (first m))] (->> (for [r (range rdim), c (range cdim)] {(+ r (- cdim c)) [(matrix-get m r c)]}) (apply merge-with into) vals)))

This worked great, but I also needed to get the diagonals going from the bottom left to the top right, which resulted in the function `reverse-diagonals`

.

(defn reverse-diagonals [m] (let [rdim (count m) cdim (count (first m))] (->> (for [r (range rdim), c (range cdim)] {(+ r c) [(matrix-get m r c)]}) (apply merge-with into) vals)))

As this was almost the same function as diagonals, with just a different function for getting the key, so I extracted a function `matrix-lines`

which resulted in:

(defn matrix-lines [m f] (let [rdim (count m) cdim (count (first m))] (->> (for [r (range rdim), c (range cdim)] {(f rdim cdim r c) [(matrix-get m r c)]}) (apply merge-with into) vals))) (defn diagonals [m] (matrix-lines m (fn [rdim cdim r c] (+ r (- cdim c))))) (defn reverse-diagonals [m] (matrix-lines m (fn [rdim cdim r c] (+ r c))))

Where the function `matrix-lines`

will generate the lines based off of a function to generate a key for a given cell.

I have seen that it is idiomatic Clojure code to use `_`

s to signify function variables that are not used, so looking at this with some fresh eyes, should those variables defined in the functions `diagonals`

and `reverse-diagonals`

be an `_`

instead, even though they are the first bindings to the function?

The last part of working with the matrix that I needed were functions to partition the diagonals, and get all the partitioned diagonals in both directions.

(defn partition-diagonals [m n diagonals-fn] (apply concat (map #(partition n 1 %) (diagonals-fn m)))) (defn partition-every-diagonal [m n] (concat (partition-diagonals m n diagonals) (partition-diagonals m n reverse-diagonals)))

The function `partition-diagonals`

returns the result of `concat`

ing every resulting seq from calling `partition`

on every result of call the `diagonals-fn`

which is the function to get the diagonals that was passed in as the second parameter. The function `partition-every-diagonal`

simply `concat`

s the results of calling `partition-diagonals`

with the functions `diagonals`

and `reverse-diagonals`

.

(defn problem11 [] (let [m [[ 8 2 22 97 38 15 0 40 0 75 4 5 7 78 52 12 50 77 91 8] [49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4 56 62 0] [81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 3 49 13 36 65] [52 70 95 23 4 60 11 42 69 24 68 56 1 32 56 71 37 2 36 91] [22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80] [24 47 32 60 99 3 45 2 44 75 33 53 78 36 84 20 35 17 12 50] [32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70] [67 26 20 68 2 62 12 20 95 63 94 39 63 8 4 91 66 49 94 21] [24 55 58 5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72] [21 36 23 9 75 0 76 44 20 45 35 14 0 61 33 97 34 31 33 95] [78 17 53 28 22 75 31 67 15 94 3 80 4 62 16 14 9 53 56 92] [16 39 5 42 96 35 31 47 55 58 88 24 0 17 54 24 36 29 85 57] [86 56 0 48 35 71 89 7 5 44 44 37 44 60 21 58 51 54 17 58] [19 80 81 68 5 94 47 69 28 73 92 13 86 52 17 77 4 89 55 40] [ 4 52 8 83 97 35 99 16 7 97 57 32 16 26 26 79 33 27 98 66] [88 36 68 87 57 62 20 72 3 46 33 67 46 55 12 32 63 93 53 69] [ 4 42 16 73 38 25 39 11 24 94 72 18 8 46 29 32 40 62 76 36] [20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 4 36 16] [20 73 35 29 78 31 90 1 74 31 49 71 48 86 81 16 23 57 5 54] [ 1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48]]] (apply max (map multiply (concat (partition-rows m 4 1) (partition-columns m 4 1) (partition-every-diagonal m 4))))))

The function `problem11`

applys the function `max`

to the result of calling `multiply`

on every possible partition of the matrix m, to get largest multiple of ‘four adjacent numbers in any direction’.

So far, this has been the Project Euler problem with the most code that was needed to solve the problem, including the ones I have solved but not posted answers to yet. While overall this is still not a great deal of code, I am wondering if there are any things that I am missing that might make this even more concise and expressive.

Is there anything that I have missed? Anything interesting in my approach? Again, I thank you in advance for any comments that you might have on this.

Thanks again,

–Proctor

### Project Euler in Clojure – Problem 10

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 6, 2012

This is my solution to Problem 10 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 10 of Project Euler is described as:

Find the sum of all the primes below two million.

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:

(defn square [n] (* n n)) (defn sum [s] (reduce + s)) (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)))))) (defn problem10 ([] (problem10 2000000)) ([n] (bigint (sum (primes-under2 n)))))

The functions sum and square came from the suggestion of Arcane Sentiment in a comment on a previous problem, as well as a post of his Square in R7RS.

The function primes-under2, is my second attempt at creating the primes under a given number using the Sieve of Eratosthenes. The short description is that the function uses sets of multiples of each integral number up to the square root of the number specifies and removes those items from the set. A more detailed write up can be found in my post Sieve of Eratosthenes in Clojure using Sets.

With those functions defined, I simply get the sum of the call to primes-under2 and make it a bigint to try to ensure the sum will be handled nicely for large numbers, but looking at it now, it is probably not even needed.

**Update**

I have posted my solution to Problem 11.

–Proctor

### Project Euler in Clojure – Problem 9 Redux

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 5, 2012

After contemplating on the comments on my previous solution to Problem 9 of Project Euler, I took a few minutes and looked into the for comprehension and then rewrote the method for generating the pythagorean triples.

I also had a comment pointing out that I was missing some triples generated, and that I was likely lucky in getting a triple that matched the criteria. When I was originally looking at wikipedia at the posting on Pythagorean Triple, I saw the following text:

Despite generating all primitive triples, Euclid's formula does not produce all triples.

I figured I was good with just generating all primitive triples, but as it was pointed out that I was missing some, I added in the functionality to generate the multiples of the triples as well.

The function pythagorean-triples has now been rewritten as:

(defn pythagorean-triples [] (for [m (range 2 500) n (range 1 m) k (range 1 500)] (map (partial * k) (pythagorean-triple-for m n))))

Thanks for the feedback, and this is much nicer, even with the extra computation for multiplying the triples by a K.

–Proctor

### Project Euler in Clojure – Problem 9

Posted by Proctor in Clojure, Deliberate Practice, Lisp, Project Euler on July 1, 2012

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