## 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 **factoria**l 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:

#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 (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?