Project Euler Problem 6 and 7 in F#

2 minute read

Project Euler problem 6 is one of the easiest that I have encountered so far. Also, Problem 7 is quite easy to solve once you have a function for prime numbers (something we did in Problem 3). Therefore, in this post I give 2 problems for the price of 1! :)

Problem 6

Let's have a look at the question for Problem 6:

The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + ... + 10^2 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

There are a few known tricks to calculate the sum of the squares; however, given the limited size of the problem at hand, brute-force is perfectly fine: it shows once more the elegance of a declarative solution.

open System

let square x = x * x

// a^2 + b^2 + ... + z^2
let sum_of_square max =
Seq.unfold (fun x -> if x > max then None else Some(x*x, x+1)) 1
|> Seq.sum

// (a +b + ... + z)^2
let square_of_sum max =
{1 .. max}
|> Seq.sum
|> square

let problem_6 max =
square_of_sum(max) - sum_of_square(max)

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

As I mentioned in the introduction, this one is fairly easy once you know how to tell whether a given number is prime or not. We did that exercise in Problem 3.

There's a catch though: this time we are counting the prime numbers. In the test we did in Problem 3 there was a small error that in that context was irrelevant: the test returned true also for 0 and 1, which strictly speaking are not prime numbers (2 is considered to be the first prime number).

For this reason, I have modified the code of is_prime a bit so that the first prime will be 2, the second 3, and so on as appropriate.

open System

let is_prime x =
let rec check i =
x > 1L &&
(double i > sqrt (double x) || (x % i <> 0L && check (i + 1L)))
check 2L

let sequence_of_first_n_primes n =
Seq.initInfinite (fun x -> int64 x)
|> Seq.filter is_prime
|> Seq.take n
|> Seq.max

Ok... break time is over. Problem 8 looks a bit more challenging. See you when I have got a nice solution for that.

Updated:

Leave a Comment