Skip to content

Project Euler Problem 62

December 15, 2011

Project Euler Problem 62 solution is based on the following consideration: if we manage to build a morphism mapping digit permutations of a number to the same hash value, then the solution can be found by one linear pass along naturals. A very simple such morphism would be breaking the number into digits and just sorting these digits into a string, using the latter as the permutations’ hash.

open System
open System.Collections.Generic

let hash n =
    n.ToString().ToCharArray() |> Array.sort |> fun x -> new String(x)

let permutations = new Dictionary<String, int*int64>()

let is5thCube permutated =
    let key = hash permutated
    if permutations.ContainsKey(key) then
        let hasOccured, cube = permutations.Item key
        match hasOccured with
        | 4 -> true
        | _ -> permutations.Item key <- (hasOccured + 1, cube)
               false
    else
        permutations.Add (key, (1, permutated))
        false

let problem062 () =
    Seq.initInfinite (fun x -> (int64 x) * (int64 x) * (int64 x))
    |> Seq.find is5thCube
    |> fun permutated -> snd (permutations.Item (hash permutated))

This task allows for an apparent generalization: finding upto n permutations of m-th power, which would translate into just few changes to the code above.

Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: