# Project Euler Problem 62

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

Leave a Comment