Project Euler Problems #1-#5

Question

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 multiples is 23.
// Find the sum of all the multiples of 3 or 5 below 1000. 
// Project Euler 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.
let rec fibsRec a b limit =
 if a + b < limit then
 let current = a + b
 let rest = fibsRec b current limit
 current :: rest
 else 
 []
// Project Euler 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 ?
let findFactors (num:int64) =
 let upperBound = int64(System.Math.Sqrt(double(num)))
 [ 2L .. upperBound ] |> Seq.filter (fun x -> num % x = 0L)
let isPrime(num:int64) = findFactors(num) |> Seq.length = 0
let findMaxPrimeFactor(num:int64) =
 let upperBound = int64(System.Math.Sqrt(double(num)))
 [ 2L .. upperBound ] |> Seq.filter (fun x -> num % x = 0L)
 |> Seq.filter isPrime
 |> Seq.max
// Project Euler 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.
open System.Linq
let isPalindrome n =
 let charArray = n.ToString().ToCharArray()
 let revCharArray = Array.rev charArray
 charArray.SequenceEqual(revCharArray)
let findLargestPalindrome numbers =
 numbers |> List.collect (fun x -> numbers |> List.map (fun y -> x * y))
 |> Seq.filter isPalindrome
 |> Seq.max
// Project Euler 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?
let evenlyDivided(num, fact) = num % fact = 0
let evenlyDividedByAll(num, facts) = facts |> Seq.forall (fun x -> evenlyDivided(num, x))
let findSmallestMultiple(numbers) =
 let max = Array.max(numbers)
 Seq.unfold (fun x -> Some(x, x + 1)) 1
 |> Seq.map (fun x -> x * max)
 |> Seq.filter (fun x -> evenlyDividedByAll(x, numbers))
 |> Seq.head
[<EntryPoint>]
let main argv = 
 printfn "Solution to Project Euler 1: %i" ([ 1 .. 999 ] |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0) |> Seq.sum)
 printfn "Solution to Project Euler 2: %i" (1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter (fun x -> x % 2 = 0) |> Seq.sum)
 printfn "Solution to Project Euler 3: %i" (findMaxPrimeFactor 600851475143L)
 printfn "Solution to Project Euler 4: %i" (findLargestPalindrome [ 100 .. 999 ])
 printfn "Solution to Project Euler 5: %i" (findSmallestMultiple [| 1 .. 20 |])
 System.Console.ReadLine() |> ignore
 0 // return an integer exit code

• Ethan Bierlein: Are these all in separate files? I noticed an open ... in the middle of your code.
• Ethan Bierlein: Also, I think you missed the inclusion of your PE1 code. There's just a comment above a blank line.
• Der Kommissar: @EthanBierlein No, they are all one file. And all the PE1 code is in the one statement, I just added the comment to remind myself that it existed.
• Mathieu Guindon: This question is being discussed on meta

Answer 1

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 <= newNumber do
 if newNumber % counter = 0L then
 newNumber <- newNumber / counter
 largestFactor <- counter
 else
 counter <- counter + 1L
 if newNumber > 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

After doing this which halved the running time, I discovered that F# doesn't have break or continue. Bummer. So I tried another version using while loops with flag variables, and this became the third variant on this solution. Extremely imperative, and kind of ugly for F# code to be (if I most say so myself!).

Here is the code:

(** Project Euler 4 : Largest palindrom of xxx*yyy ********************)
let findLargestPalindrome_v2 maximum minimum=
 seq { for x in { maximum .. -1 .. minimum } do
 for y in { x .. -1 .. minimum } do
 yield x * y }
 |> Seq.filter isPalindrome
 |> Seq.max
let findLargestPalindrome_v3 maximum minimum=
 let mutable maxPalindrome = 0
 let outer_max = maximum
 let outer_min = minimum
 let inner_min = minimum
 let mutable i = outer_max
 let mutable outerLoop = true
 while outerLoop do
 let mutable innerLoop = true
 let inner_max = i
 let mutable j = inner_max
 while innerLoop do
 let product = i * j
 if product < maxPalindrome then
 innerLoop <- false
 if isPalindrome product && product > maxPalindrome then
 maxPalindrome <- product
 j <- j - 1
 if j < inner_min then 
 innerLoop <- false
 i <- i - 1
 if i < outer_min then
 outerLoop <- false
 maxPalindrome
let euler_4_org() = findLargestPalindrome [ 100 .. 999 ]
let euler_4_v2() = findLargestPalindrome_v2 999 100
let euler_4_v3() = findLargestPalindrome_v3 999 100

And here are the timings:

Solution to Project Euler 4
 Org: 906609 in 596.487700 ms
 v2 : 906609 in 256.063700 ms
 v3 : 906609 in 4.038000 ms

Quite a substantial effect to do the imperative version, even in F#.

Problem 5: Smallest multiple

Even for the final problem you still opted for the brute force, and this took 4 seconds in my environment to solve. After googling a little I found yet another faster imperative solution.

But for this problem I do believe there should be a possibility to find a neater functional solution. Reasoning is that instead of doing the brute force alternative, one could find the prime factors of the different numbers from 1 through 20, and then find the minimum number of factors in order to represent all numbers. In other word, to get 16 you need to have at least 4 times the number 2, but this also gives the 2, 4, 8 and parts of all the even numbers. You need at least 2 times the number 3 to get 3 and 9. And so on.

Added: After a discussion chat related to avoiding mutable, I compiled a new variant using Seq.reduce included in code below.

But here are some faster alternatives:

(** Project Euler 5 : Smallest multiple of 1..20 **********************)
let smallestMultiple top =
 let mutable prod = 1
 for i in { 1 .. 20 } do
 let prevprod = prod
 while prod % i <> 0 do
 prod <- prod + prevprod
 prod
let rec reduce_helper original previous divisor =
 if previous % divisor = 0 then
 previous
 else
 reduce_helper original (previous + original) divisor
// Could replace the anonymous fun in the next segment 
let smallestMultipleReducer original divisor = 
 reduce_helper original original divisor
let smallestMultipleUsingReduction top =
 seq { 1 .. top } 
 |> Seq.reduce (fun original divisor -> 
 reduce_helper original original divisor )
let euler_5_org() = findSmallestMultiple [| 1 .. 20 |]
let euler_5_v2() = smallestMultiple 20
let euler_5_v3a() = smallestMultipleUsingReduction 20
let euler_5_v3b() = smallestMultipleUsingReduction 20

With timings:

Solution to Project Euler 5
 Org: 232792560 in 4108.854600 ms
 v2 : 232792560 in 0.099500 ms
 v3a: 232792560 in 0.700700 ms
 v3a: 232792560 in 0.023000 ms

Notice how the timings on v3a and v3b using Seq.reduce are not the same, even though the code is identical. So my timing method, might be a little off, and there seems to happen stuff under the hood optimising code when it's being executed the second time or something like that.

Rewrite of smallestMultiple to avoid mutable

After a little discussion in chat on whether it was possible to avoid the mutable in this solution, I sat down and compiled this variant:

General findings regarding speed and coding style

• It seems it is way faster to use sequences rather than list (or arrays) to fill the pipe lines. So choose wisely to achieve faster run times
• Instead of using Seq.filter (fun x -> ... ) predefine the predicate or other helper functions to get an order or so faster code. Please verify that this is the case, as it seems there is stuff under the hood which might optimize thing here and there
• For multiline comments use (* ... *) :-)
• And finally, and this came as a bit of surprise to me: Even though F# is supposedly meant to be fast for handling brute force solution to something like these Project Euler problems, implementing the imperative solution resulted in a speedup from 100 to almost 50000 times your code.
• And as Ethan Bierlein comments, you might want to look into whether to use List.map and List.collect versus Seq.* as they have slightly different meaning, and different timings and idiomatic consequences.

All code presented here is available at https://repl.it in this code block. Hope this has some value to you, even though most of this review is presenting alternate solutions.

• Ethan Bierlein: While this is a good answer in terms of performance, I'd say that it doesn't really encourage good succinct functional programming. For example, you tell the OP to not use List.collect and List.map, yet this would be the succinct way to functionally program it.
• holroy: @EthanBierlein, I'm a newbie myself, but if you use List.collect and List.map isn't that kind of building/expanding the lists instead of using the generated sequences? To me the latter seem preferable...
• Ethan Bierlein: List.collect and List.map re-generate the sequences based on a rule. While it is more performant to simply just generate a new sequence, it's more of a micro-optimization that makes the code harder to read, and a little less idiomatic.
• RobH: Did you get the code for Euler 3 from here? mathblog.dk/project-euler-problem-3 your code looks like a straight port to F# of that code.
• holroy: @RobH I don't remember. Don't think so, but solutions tend to look alike fast when they are based on the same algorithm.