Problem #62 concerns perfect cubes whose digits are rearrangements of each other. The question reads:
Project Euler Problem 62: Cubic permutations
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.
My solution for this problem falls into the category of brute force. It takes over 20 seconds to run, so I’d like to look for a more efficient solution to this question at some point. Here is my solution:
Solution #1: Brute Force Approach
We simply list all perfect cubes of each number of digits until we find a quintuple of cubes which are all rearrangements of the digits in the other cubes. As you might imagine, this process can take a while. To determine if 2 numbers are permutations of each other, I sorted the list of digits in each and checked if the results were equal. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #62
'''
import time
def isPermutation(a,b):
c = str(a)
d = str(b)
if(len(c)!=len(d)):
return False
return sorted(c) == sorted(d)
def projectEulerProblemSixtyTwo(n):
c = 345
found = 0
current = -1
cubes = []
currCube = c**3
while(found<n):
c+=1
v = c**3
if(len(str(v))>len(str(currCube))):
cubes = []
currCube = v
t = 0
first = -1
for a in cubes:
if isPermutation(a,currCube):
if(first==-1):
first = a
t+=1
if(t==4):
found+=1
current = first
cubes.append(currCube)
return current
start = time.time()
print projectEulerProblemSixtyTwo(1)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
127035954683
--- 21.7080910206 seconds ---
for input of n = 1.
'''
Yikes. That took over 20 seconds to run. Also, looking back on it, I never checked that the number has exactly five rearrangements. This code will only find numbers with at least five rearrangements. I would like to return to this problem to search for a more efficient solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 