Claudio Cherubino's blog Life of a Googler


Project Euler in F# – Problem 20

Project Euler's Problem 20 was trickier than I expected.

I'm quite sure that there is a smart solution, but there is also a "dumb" one and this is the one I'm going to present you.

The problem says:

n! means n × (n ? 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

Evaluating the factorial is straightforward in any functional language, but it is even easier in F# since the language already provides us with the factorial function.

As usual, let's show the code and then analyze it:

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 (factorial 100I)

The open directive at line 2 permits the use of the BigInt namespace, which is needed when working with very large numbers.

Then we have the code to sum the digits of a number, which is easily implemented with pattern matching.

The algorithm is based on the modulus operator, since taking the last digit of a number is equivalent to taking the remainder of the number itself divided by 10 (in a base 10 system).

Hence, we take the last digit and recursively apply the same function to the rest of the number, until there is only one digit left, i.e. the number is less than 10.

This operation is done by the divmod function, which returns the integer quotient and the remainder as a couple (x, y).

You may have noticed that there is a capital "I" after each number. That letter stands for Big Integer and is used to distinguish them from normal integers.

It's done, we just have to apply the digits function to the output of factorial 100I.

Why did I call this solution "dumb"?

Because I had to compute 100! (which is a number with 158 digits) and then sum its digits, but this solution is not feasible if the number becomes much larger.

I think that there should be some mathematical trick to do the same job, but I don't know it.

Does anybody have a different approach to suggest?

Comments (0) Trackbacks (1)

Leave a comment