FSharp.it

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?

Once in a while I give a look at the web server log to find out how people landed in this blog and yesterday there was someone that entered the following search string into Google:

Given a random List of integers, write a function that removes all the duplicate values

This site appears as the first result, even if there is no solution for that problem, but I want to help you anyway, unknown visitor!

In fact, we can make use of the Set data type to easily solve the problem.

According to the definition, a Set represents a collection of elements without duplicates.
So, if we create a Set from the given list, all duplicate values will be automatically filtered.

This can be done in a single line, I’ll call the function nub because this is the name of the corresponding Haskell one:

let nub xs = xs |> Set.of_list |> Set.to_list

As I said, to return a List without duplicate values we just need to create a Set from it and then create a List from the new Set.

Do you think it is fair to act this way or should I say that I’m cheating?

A long time has passed since I last posted the solution of one of Project Euler’s problems.

Problem 45 is related to figurate numbers, i.e. numbers that can be represented as geometrical patterns.

In particular, we are going to find a number that is triangular, pentagonal and hexagonal at the same time:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle: Tn=n(n+1)/2
Pentagonal: Pn=n(3n−1)/2
Hexagonal: Hn=n(2n−1)

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

A trivial solution will be computing the lists of triangular, pentagonal and hexagonal numbers and then find their intersection. However, we don’t know how big the searched number can be, so we are not able to determine when to stop the generation of each list.

Hence we need a smarter solution, based on the mathematical properties of these numbers.

First of all, every hexagonal number is also a triangular number, so our problem is reduced to finding the smallest hexagonal pentagonal number greater than 40755.

Then we can generate the hexagonal numbers and check whether they are also pentagonal, stopping at the first one found.

According to the definition, we can test if a positive integer x is a pentagonal number by computing:

If n is an integer, then x is the nth pentagonal number. If n is not an integer, then x is not pentagonal.

Let’s look at the F# code:

#light
open System
open Microsoft.FSharp.Math.BigInt

let hexagonal n = n * (2I * n - 1I)
let isPentagonal x = ((sqrt(to_float (24I * x + 1I)) + 1.0) % 6.0) = 0.0

let nums = 144I |> Seq.unfold (fun i -> Some (i, i + 1I))
let answer = nums |> Seq.map hexagonal |> Seq.find isPentagonal

At lines 5 and 6 we define the functions to compute the nth hexagonal number and to check if an integer x is pentagonal.

Then we start generating the hexagonal numbers to be tested, starting from the 144th, since the solution must be greater than 40755, that is the 143th hexagonal number.

In the last line we just return the first number for which isPentagonal is true, without having to know when to stop thanks to lazy evaluation, which allows us to continue generating numbers only when actually needed.

The solution to the problem is greater than I could imagine, that’s why we need to use BigInt instead of normal integers.

What do you think about the approach I followed to solve this problem?

The mathematical exercise we are going to solve comes from mathschallenge.net and can be summarized in a single sentence:

Find the smallest multiple of nine containing only even digits.

We just need a function to check if a number contains only even digits and then pass to it the multiples of nine.

This algorithm can be translated into the following code:

#light
open System

let isEven n = (n % 2 = 0)

let rec allEvenDigits n =
    match n with
    | n when n < 10 -> isEven n
    | n -> (isEven (n % 10)) && (allEvenDigits (Int32.div n 10))

let nums = 9 |> Seq.unfold (fun i -> Some (i, i + 9))

let answer = Seq.find allEvenDigits nums

The isEven function is just a “shortcut” for the modulus operator and it is used inside allEvenDigits, where it is applied to each digit of the given number.

Then, we have to generate the multiples of nine, but we don’t know when to stop, so we need an infinite sequence, that can be produced by the Seq.unfold function.

At the end we use Seq.find, which takes a boolean function (allEvenDigits) and a sequence (nums), and returns the first element of the sequence for which the given function returns “true”, i.e. the smallest multiple of nine containing only even digits, that is exactly what we had to find.