Claudio Cherubino's blog Life of a Googler

30Apr/084

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?

Comments (4) Trackbacks (0)
  1. I don’t want to be a troll but this:

    number = 0
    for e in xrange(1000):
    number += e ** e
    str(number)[-10:]

    seems to be easier and (a bit) more readable.
    HAND

  2. I agree that your solution may be easier to understand, but it is not written according to the functional programming paradigm, is it?

    BTW, which language is that? Python? Ruby?

  3. …mmm…

    Ciao Claudio.

    And if you generate the sequense of pow, next map the last10 function for each pow and at end sum all the numbers?

    …mmm…

  4. Hi Salvo,
    your idea can be implemented with this code:

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

    However, the sum of all these 10-digits numbers results in a number (4629110846700) which contains 13 digits!

    We are actually forced to apply the last10 function another time at the end…


Leave a comment

(required)

No trackbacks yet.