Add-ins:
Excel
PowerPoint

The cube, 41063625 (345^{3}),
can be permuted to produce two other
cubes: 56623104 (384^{3})
and 66430125 (405^{3}).
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.

This is another problem that one can solve in Excel without any VBA support.

Before we can address the problem itself, we must address a basic
question. How does one figure out if one number is a
permutation of the digits of another number? I solved this
with the following approach. Map each number into a 10
character string (we could have used an array but it is a lot easier
dealing with strings in Excel). The *position* in the
string represents a specific digit. The character in that
position represents the frequency with which that digit occurs in
the number. Hence, the first character (position 1) corresponds
to the digit 0. So, if the digit 0 occurs 4 times in the
number the first character in the string will be 4. To deal
with frequencies greater than 9, I decided that the frequency would
be stored using the hexadecimal system. Now, to check if one
number is a permutation of the digits of another number, all we have
to do is check the corresponding digit maps. If they are the
same the numbers are permutations. If not, they are not.

With this out of the way, we can address the specifics of the problem. Since the description of the problem includes 3 permutations and 3 digit numbers, my guess was that five permutations would require at least a 4 digit number. So, I picked the range 999 to 10,000.

An advantage of picking an upper limit of 10,000 is that 10000^{3}
is a 13 digit number. Since Excel supports 15 digits of
precision the range of interest is within the program's capabilities.

Next, we need to figure out how to map the cube of a number into its digit map and then check how often each digit map occurs in the range of numbers from 999 to 10,000. The base number will be in column A starting with row 2. In column B calculate the cube of the number. In column C calculate the number of digits in the cube. In the 13 columns D:P extract the individual digits of the cube. In Q:Z calculate the frequency of each of the digits 0 through 9. In AA concatenate the frequencies to get a single 10 character string. This is the digit map for the cubed number. In column AB calculate the frequency with which the digit map occurs. Finally, in AC2 calculate the cubed value corresponding to a frequency of 5 in column AB.

Start by entering in A2 the value 999.

B2 contains the formula =A2^3. C2 contains the formula =INT(LOG10(B2))+1 though it could just as easily contain the formula =LEN(B2).

D2:P2 contain the *array* formula =MID(B2,COLUMN(INDIRECT("1:"&$C2)),1). To enter an array formula complete the formula with the CTRL+SHIFT+ENTER key combination rather than just the ENTER or TAB key. If done correctly, *Excel* will show the formula enclosed in curly brackets { and }

To compute the frequency of the digits, start by entering the digits 0 through 9 in Q1:Z1. Then, in Q2 enter the formula =DEC2HEX(COUNTIF($D2:$P2,Q$1)). Copy Q2 to R2:Z2. Next, create the digit map in AA2 with the formula =Q2&R2&S2&T2&U2&V2&W2&X2&Y2&Z2. Since we started with the number 999 in row 2 the number 10,000 will be in row 9003 (10000-999+2). Finally, in AB2 enter the formula =COUNTIF($AA$2:$AA$9003,AA2)

In A3 enter the formula =A2+1. Copy B2:AB2 to row 3. Copy A2:AB3 down to rows 4:9003.

Finally, in AC2 enter the formula =INDEX(B:B,MATCH(5,AB:AB,0)). This will be the answer to this Project Euler question.