Project Euler Problems #1-#5

Since I've been playing with F#, I decided to try my hand at implementing some of the Project Euler problems, and I've been having a blast doing it. (f#-is-fun)

So, I'm going to list all the Project Euler problems I solved to make things pretty clear:

Project Euler Problem 1: Multiples of 3 and 5


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.

Solution:



233168


Project Euler Problem 2: Even Fibonacci numbers


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.

Solution:



4613732


Project Euler Problem 3: Largest prime factor


The prime factors of 13195 are 5, 7, 13 and 29.


What is the largest prime factor of the number 600851475143 ?

Solution:



6857


Project Euler Problem 4: Largest palindrome product


A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.


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

Solution:



906609


Project Euler Problem 5: Smallest multiple


2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.


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

Solution:



232792560


And here is all the F# code to make these happen:

```
// Project Euler 1: Multiples of 3 and 5;
// 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 m

After working for far too long on this, here is a review focusing mainly on performance issues, and possibly introducing some non functional stuff along the way. Lets take it problem by problem.

But let me start by stating that your code looks nice and clean, and without knowing any official style guides for F#, it is quite readable once you get a hang of the different F# idioms. One thing I think someone might mention though is to gather the open ... stuff at the beginning, and possibly to use multiline comments here and there.

Problem 1: Sum of multiples of 3 and 5

This being a rather simple variant, one could think there isn't much to optimize, but I found two issues to optimize your variant:

• Instead of using a in-place function as predicate for Seq.filter use a predefined predicate. This cut down the time to 10 % of original time

• Instead of using a list, use a sequence to fill the pipe, this reduce the time by a third or so

But the really large saving is by changing algorithm to use the following formula for calculating the sum of factors of n below k: \$(n m (m + 1)/2\$ where \$m = (k - 1) / n\$. See https://codereview.stackexchange.com/a/280/78136 for more information on this rather fast imperative solution.

Using the following code for timing a function in F#:

(** My timing function ************************************************)
let time f =
  let sw = System.Diagnostics.Stopwatch()
  sw.Start()
  let res = f()
  sw.Stop()
  (res, sw.Elapsed.TotalMilliseconds)

And the following extra code for first problem:

(*******  Project Euler 1 : Sum of multiples of 3 and 5 ***************)

let sumFactorsOfNBelowK k n = 
    let m = ( k - 1 ) / n
    n * m * ( m + 1 ) / 2

let mod3or5 x =
    x % 3 = 0 || x % 5 = 0

let euler_1_org() = [ 1 .. 999 ] |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0) |> Seq.sum
let euler_1a_org() = [ 1 .. 999 ] |> Seq.filter mod3or5 |> Seq.sum
let euler_1b_org() = { 1 .. 999 } |> Seq.filter mod3or5 |> Seq.sum

let euler_1_v2() = sumFactorsOfNBelowK 1000 3 + sumFactorsOfNBelowK 1000 5 - sumFactorsOfNBelowK 1000 15

With a test block similar to:

let (euler1, time1) = time euler_1_org
let (euler1a, time1a) = time euler_1a_org
let (euler1b, time1b) = time euler_1b_org
let (euler1_v2, time1_v2) = time euler_1_v2

printfn "Solution to Project Euler 1"
printfn "  Org: %i in %f ms" euler1 time1 
printfn "    A: %i in %f ms" euler1a time1a 
printfn "    B: %i in %f ms" euler1b time1b 
printfn "   v2: %i in %f ms" euler1_v2 time1_v2

I got the following output for problem 1:

Solution to Project Euler 1
Org: 233168 in 3.990900 ms
A: 233168 in 0.378200 ms
B: 233168 in 0.260800 ms
v2: 233168 in 0.037700 ms


Problem 2: Summing even Fibonaccy numbers

This one I tried various versions, but didn't find that much to optimize as it seems like your fibsRec is quite fast. Using the same trick as in previous problem, I almost halfed the time using a predefined isEven function.

Here is code:

(** Project Euler 2 : Sum of even Fibonacci under 4 million ***********)

let isEven n =
    n % 2 = 0

let euler_2_org() = 1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter (fun x -> x % 2 = 0) |> Seq.sum
let euler_2_v2() = 1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter isEven |> Seq.sum

And my output was:

Solution to Project Euler 2
Org: 4613732 in 0.592100 ms
v2a: 4613732 in 0.354700 ms


Problem 3: Max prime factor under n

As you most likely are aware of most of your solutions are brute force solutions, and therefore there does exist much faster solutions. I tried various alternatives, but soon found that doing stuff functional and with large numbers was as neat as I thought it should be. I guess the .Net shines through here somewhat.

An alternate implementation (mostly imperative) follows:

(** Project Euler 3 : Max prime factor under 600851475143L ************)

let findMaxPrimeFactor_v2 (number:int64) =
    let mutable newNumber:int64 = number
    let mutable largestFactor = 0L

    let mutable counter = 2L
    while counter * counter  largestFactor then
       largestFactor <- newNumber

    largestFactor

let euler_3_org() = findMaxPrimeFactor 600851475143L
let euler_3_v2() = findMaxPrimeFactor_v2 600851475143L

With timings:

Solution to Project Euler 3
Org: 6857 in 118.639500 ms
v2 : 6857 in 0.115400 ms


You could most likely shave a lot of your timings using sequences, change the step value, using predefine predicates and not to say using a prebuilt prime list (or memoization of some sort). I didn't get around doing that. I just implemented a way faster method... :-)

Problem 4: Largest palindrome product

Here I tried a little harder to actually follow your code and do some optimization on it. And the main optimization was the following two issues:

• Replace the List.collect and List.map with a sequence of double for loop

• Change the loop to go downwards from 999 to 100 instead of upwards

Aft

StackExchange Code Review Q#113106, answer score: 6