Claudio Cherubino's blog Life of a Googler

Project Euler in F# – Problem 48

The following problem from Project Euler is one of those supposed to be solved either with intensive computation or a "smarter" approach.

Here is the description of problem number 48:

The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

If our language allows us to evaluate the series mentioned above (and F# does!), we can just do it and then take the last 10 digits of the result as required.

This can be implemented by the following F# code:

#light
open Microsoft.FSharp.Math.BigInt

let last10 num = num % (pow 10I 10I)

let answer = [1I .. 1000I] |> Seq.map (fun x -> pow x x) |> Seq.fold (+) 0I |> last10

The first problem is extracting the last ten digits from a given number, and this is done by dividing the number by 10^10 and returning the remainder of the division (line 4).

Then we have to generate the series n^n for all n from 1 to 1000 and sum the items.

This sum is actually a huge number (more than 3000 digits) but we are only interested in the last ten digits, so we can use the pipeline operator (|>) to pass it to the last10 function.

The only caveat is to use BigInt, otherwise the numbers we are talking about will never fit into the other numeric data types.

Easy, isn't it?

#light
open Microsoft.FSharp.Math.BigInt

let rec digits n =
    match n with
    | n when n < 10I -> n
    | n ->
        let x, y = divmod n 10I
        y + digits x

let answer = digits (pow 2I 1000I)