Project Euler 62: Find the smallest cube for which exactly five permutations of its digits are cube

Project Euler 62: Find the smallest cube for which exactly five permutations of its digits are cube

Written by on 24 September 2011

Topics: Project Euler

Problem 62 of Project Euler goes

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

I figured the problem could be attacked from two sides

  1. We generate numbers and check how many cubes exists of the number and its permutations
  2. We generate cubes until we find 5 that gives the same permutation

I couldn’t wrap my head around the first approach, and I think it would take an awful lot time since we would be dealing with a whole lot of numbers which are not cubes. Besides it is more expensive to calculate the cube root of a number than it is to go the other way.

Solution approach

So approach number two was fairly obvious for me. The challenge was to figure out if two cubes were permutations of each other and keep track of how many cubes of a certain permutation we already have.  I decided to use a SortedList for that purpose. It takes a key and a value. I decided that the key for a certain number should be a given permutation, in which case I chose the largest number I could generate. so 28^3 = 21952 would generate the key 95221. The value to store was the number of times a cube gave us this permutation. Then I just needed to keep generating cubes until the value of one entry reached 5.

However, one last challenge that remained was how to go from the permutation to the smallest cube? I decided to change the value from a simple integer to a small object containing both the number of times the permutation had been generated as well as the smallest cube generating that number.

The code

That class looks like

class Cube{
    public long N { get; set; }
    public int Perms { get; set; }
}

The method for generating the largest permutation looks like

public long makeLargestPerm(long n) {
    long k = n;
    int[] digits = new int[10];
    long retVal = 0;

    while (k > 0) {
        digits[k % 10]++;
        k /= 10;
    }

    for (int i = 9; i >= 0; i--) {
        for (int j = 0; j < digits[i]; j++) {
            retVal = retVal * 10 + i;
        }
    }

    return retVal;
}

The main loop for this problem looks like

long n = 345;
SortedList cubes = new SortedList();

while (true) {
    n++;
    long smallestPerm = makeLargestPerm(n*n*n);
    if (!cubes.ContainsKey(smallestPerm)) {
        cubes.Add(smallestPerm, new Cube {N=n, Perms = 0});
    }

    if (++cubes[smallestPerm].Perms == 5) {
        result = cubes[smallestPerm];
        break;
    }
}

Wrapping up

So far I have shown you a solution approach for the problem of find a cube which permutations are also cubes. But how does it perform. Well running it on my computer gave me the following:

The smallest cube with 5 permutations is 127035954683
Made from 5027^3
Solution took 15 ms

So I am fully satisfied with the solution speed. I think I have shown most of the source code, but you are as always welcome to take a look at the file to get the full overview.

Did you approach it differently? Do you have suggestions for optimization either for speed or readability? Other comments? Don’t be shy use the small box below and let me hear your voice.

The image of cubes was taken by Marius Watz and shared under the creative commons license. The derivative work I have made from it is shared under the same conditions.

7 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    Any reason for why you pick SortedList over Dictionary or SortedDictionary?
    I did some tests with your solution and either SortedList or Dictionary is the fastest.

    Cool solution, though.

  2. Kristian says:

    Hi SuprDewd

    No there is no specific reason for me to have picked the SortedList. It was the first class I found which suited my needs and to be honest I didn’t think about it any further.

    Testing it now with your suggestions I can clock the Dictionary to 4ms which is a significant speed up in this problem. So I should have used that. Thanks for pointing me in that direction.

    I looked into it a bit more and found the following comparison of different build in classes in .Net from Vladimir Bodurov. It gives some insight in which class to pick for which problem.

    Thanks once again for enlightening me in areas I wouldn’t have found otherwise.

    /Kristian

  3. Khaur says:

    I proceeded in a very similar way, except I didn’t use the largest permutation as a representation for the class of permutations. Here’s what my function looks like:

    /* "Hashes" a number so that collisions will occur on digit permutations.
     * Undesired collisions may occur if the number of digits of n in the base exceeds the hashbase.
     */
    template<class T>
    T permHash(T n,int base=10, int hashbase=10){
      T value=0;
      while(n!=0){
        value+=pow(hashbase,n%base);
        n/=base;
      }
      return value;
    }
    

    It is not very dense, but it is easy to compute and gets the job done. It would be interesting to see how dense a hash we could get while keeping a rather simple function.

    Also, I wipe my equivalent to your sorted list every time I reach a new power of 10 to reduce access times and memory impact (it also allows me to change hashbase).

    By the way, great job with this blog!

  4. Shobhit says:

    I follow your blog regularly.
    Most of the time you stump me with your clever approach (e.g. problem 61) and get much better solution than me :). Keep up the good work !!
    For this problem, I followed a similar approach with two exceptions.
    1) How to find a key for a given cube? I generate the smallest possible number and convert it to a string key. To do that, I convert the number to a char array, sort it and make a string of the sorted char array. The code is fairly small. I used a string key because I was not sure about the integer key. For example, 1024 would give 0124 as the key. .Net would remove the preceding 0 and will make 124 as a key which may give wrong result.
    private string FindKey(long number)
    {
    char[] numaschararray = number.ToString().ToCharArray();
    Array.Sort(numaschararray);
    string key = new string(numaschararray);
    return key;
    }
    2) Instead of using an object, I used a complex dictionary where key is the string and the value is a List of long integers.
    Dictionary<string, List> hashlist = new Dictionary<string, List>();
    The numbers (cubes) which result in the same key are added to the list.
    I stop when the list.count is 5.
    Creating objects is a pretty big overhead. Adding numbers to the list is very quick. I get 6 ms.

  5. I think this solution first finds the smallest cube that has four smaller permutations, then reports the smallest of these.

    I made a similar mistake (using a different algorithm) and came up with 140283769536 because I did not look at all cases with 12 digits.

    To be correct and not just lucky, you need to run through all cases with a particular number of digits, then select the smallest result with 5 permutations.

    By your algorithm, you risk finding permutations in this order: x1, y1, y2, y3, y4, y5, x2, x3, x4, x5 and stopping after you find y5, reporting y1. But the answer is x1.

    In this case for 12 digit numbers I believe there are two sets of five whose sequence is x1, y1, x2, x3, y2, x4, x5, y3, y4, y5. By your algorithm, x5 < y5, therefore x1 is reported, correctly.

    That is my claim, I could be wrong.

  6. Jean-Marie Hachey says:

    Results in Table 1 were obtained with Sir Alan’s (1) algorithm after these two modifications:
    1) Reference added: System.Numerics
    2) BigInt replaced by BigInteger

    http://img15.hostingpics.net/pics/272286pe62tab1cub.jpg

    ___

    Sources:

    1) PROJECT EULER #62
    http://siralansdailyramble.blogspot.ca/2009/04/project-euler-62.html
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  7. psykid says:

    great solution, but i think there is one issue unaccounted for.. the question asks for exactly 5 permutations not less not more.. so what if the given solution have more than 5 permutations?

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.