Project Euler Problem 6 and 7 in F#

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.