Claudio Cherubino's blog Life of a Googler

20Mar/092

Project Euler in F# – Problem 52

After a long break, let's resume with the Project Euler series.

The next one to be solved is Problem 52:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

As usual, we have to break the problem into small pieces and solve these pieces one by one.

As in many other Project Euler problems we have to extract the digits of a number, and this is done by converting the number into a string (i.e. an array of characters) and then casting the characters to integers.

We also need a function to check if two numbers are made of the same digits. For each number we create a set from the sequence of its digits, in order to ignore the order of the items and discard duplicates. Then we apply the standard set comparison operator to get the result.

We have to multiply each positive integer by 2, 3, 4, 5 and 6, so we can define the multiples function, which takes an integer x and returns a list containing five elements, corresponding to 2x, 3x, 4x, 5x and 6x.

Thanks to these three functions, checking if a number and its multiples contain exactly the same digits is very easy. In fact, we generate the list of multiples and test all of them with the same_digits function.

The algorithm to get the answer to the problem is the following: generate an infinite list of integers (remember seq_unfold?), test each number with the check function and return the first value that passes the test.

#light

let digits n =
  n.ToString() |> Seq.map (string >> int)

let same_digits a b =
  Set.equal (Set.of_seq (digits a)) (Set.of_seq (digits b))

let multiples n =
  [2 .. 6] |> Seq.map (fun x -> n * x)

let check n =
  n |> multiples |> Seq.for_all (same_digits n)

let answer =
  1 |> Seq.unfold (fun i -> Some (i, i + 1)) |> Seq.first (fun x -> if check x then Some (x) else None)

There is also a well-known (and tricky) solution for this problem, which was presented in the book "The man who calculated". Did you know it?

Comments (2) Trackbacks (0)
  1. Why do the Seq.map in digits? I tried it with just n.ToString() and it seemed to work fine, though I had to change the signature to
    let digits (n : int)

  2. I used Seq.map because I wanted to get a sequence of integers and not a string.

    With my code, if we pass 123 as input we get [1; 2; 3;].
    Without Seq.map, with the same input we get the string “123″ which is an array of characters and not integers.

    However, in this case there is no difference for the final output, so using Seq.map could be avoided.


Leave a comment

(required)

No trackbacks yet.