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?
Project Euler in F# – Problem 16
This time we are gonna "cheat".
As in Problem 20 we have to sum the digits of a number, so we can just copy and paste the whole code and edit a single line to have a working solution.
The problem says:
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
The only difference between this exercise and the last one is the number to evaluate.
However, as for the factorial, F# already provides us with a native function for the powers of a numbers, so the final code will be:
#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)
If you compare this exercise with the last one, you can see that we actually changed one line, i.e. line 11.
Do you really want me to explain this code?
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:
#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?
Twitter Updates
- @Sabrina_Miso Che ne pensi di Community Manager per Google? In caso contattami ;) http://t.co/tBQ2e0N9 #stage #casaeditrice 1 week ago
- @MarcoEscher chi si rivede! In bocca al lupo per il tuo cammino e chissà che magari un giorno tu non mi raggiunga in Google! ;) 2 weeks ago
- @pigatss you should give one to me because I hosted you for lunch at the Googleplex :) #volunia 3 weeks ago
- Avete visto quante posizioni per italiani sono aperte in Google a Dublino? http://t.co/ZlUfZ4uA 2012-01-10
- @thetarro congratulations, I gained 4 kg in 4 weeks :( 2012-01-08
- More updates...
Posting tweet...
Follow me
