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?

4 Comments »

claudio on March 20th 2009 in Project Euler

4 Responses to “Project Euler in F# – Problem 52”

  1. Freed Myers responded on 21 Mar 2009 at 9:41 am #

    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. claudio responded on 21 Mar 2009 at 5:18 pm #

    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.

  3. Darrell Plank responded on 18 Dec 2009 at 1:51 pm #

    It would appear that your definition doesn’t work for multiple identical digits. In particular, you say you create a set partially to discard duplicates when really you don’t want to do that or you end up saying that “122″ has the same digits as “12″. It apparently works in this particular case, but strictly speaking, you should be checking the frequency of each digit’s occurence in addition to it’s mere presence. The fact that this solution works is, to some extent, luck.

  4. claudio responded on 18 Dec 2009 at 2:47 pm #

    The problem statement is ambiguous and it is not clear if repeated digits are allowed or not, but I have to agree with you that checking the frequency of each digit’s occurrence is a safer approach.

Trackback URI | Comments RSS

Leave a Reply