Project Euler Part I

August 12, 2021

Project Euler is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts adults and students interested in mathematics and computer programming.”

I must admit, mathematics is intimidating, at least for me. Its challenging but rewarding. Really most like test driven development. Intimidating but also rewarding.

First problem of the Euler project:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

So, how to tackle this one? Let’s write some test first:

(ns project-euler.core-spec
  (:require [speclj.core :refer :all]
            [project-euler.core :refer :all]))

(describe "sum of multiples"
  (it "number is 0"
    (should= 0 (sum-of-multiples [2] 0 )))
  (it "sum 2"
    (should= 2 (sum-of-multiples [2] 4 )))
  (it "sum 20"
    (should= 20 (sum-of-multiples [2] 10 )))
  (it "3 as multiplier"
    (should= 18 (sum-of-multiples [3] 10 )))
  (it "sum correctly with two multipliers"
    (should= 23 (sum-of-multiples [3 5] 10 )))
  (it "should solve euler project problem"
   (should= 233168 (sum-of-multiples [3 5] 1000))))

I noticed that the problem only wanted the sum of multiples of only 3 or 5. I could have just hardcoded the 5 and 3 in my algorithm, and that would have been easier, but as I wrote the first test I got the idea these 3 and 5 wills be parameters of a function that returns the dividends of each and them sum them. My idea came from my approach to any problem. Divide the problem into smaller problems.

Dividing the problem came to this smaller problems:

• Find a list of multipliers for the number n that are divisible by the number 5 or 3, in this case div.
  • This function can be reused to find the multipliers of any number. In our case we can use it for searching 5 and 3.
  • This function also looped over from n-1 down to but not including 0. If
• Loop over the list of [5 3] and apply the previous function to each 5 and 3 as div and the n this case 1000. This ended up in our main function.
• Once we’ve applied the first function to the list we end up of two lists, each holding the multipliers.
• We then join those two list and sum them up! Right?!

Gotcha!~

• When we join these two list we have to make sure there are no duplicated values! Thank God for Clojure set! After we make sure there are no duplicates, then we can sum the list, hello reduce + or (apply + vec)!

2nd Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Fibonacci sequence is straight forward, but 4 million?! It we do this straight recursion we will just get a stack overflow error. Only way to do this without blowing the stack is to do this with tail recursion.

I’ve also learned about how to deal with big number in clojure.

Clojure provides a set of alternative math operators suffixed with an apostrophe: +’, -’, *’, inc’, and dec’. These operators auto-promote to BigInt upon overflow, but are less efficient than the regular math operators.

Alright other than the stack overflow issue and knowing how to add big number, we tackle the problem the same way, lets break the problem into smaller problems:

• Fibonacci sequence generator using tail recursion and +'.
• Let’s pipe that sequence and filter out the one that are higher than 4M.
• From than filtering result lets filter even more with even? to get only even number.
• Finally, we just sum these up (apply +)

On to the next one!

3rd Problem

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Here we take advantage that we already have our own prime generator from a previous kata. We just generate the sequence sort it ascending and get the last element in the sequence!

More to come tomorrow!

Written by Edgardo Carreras.