Skip to main content

Project Euler Problem 62 solution with python

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.
Even though this problem talks about permutation, we should not think of permuting each and every cube to get our answer. This will consume a lot of resources and the answer will probably take days.
But after scratching my head for many days I was able to arrive at a solution. The algorithm works on the basics of permutations. I will exaplain you the basics first.
Consider two lists - [1, 2, 3] and [3, 2, 1]. Now lets check the permutations of these two lists.
In [1]:
# importing permutations function
from itertools import permutations

# first list
list_1 = [1, 2, 3]

# second list
list_2 = [3, 2, 1]

# check if both the lists are same
print (list_1 == list_2)

print "First List"
# lets print the permutations of first list
for i in permutations(list_1):
    print i

print "Second List"
# lets print the permutations of second list
for j in permutations(list_2):
    print j

False
First List
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Second List
(3, 2, 1)
(3, 1, 2)
(2, 3, 1)
(2, 1, 3)
(1, 3, 2)
(1, 2, 3)
If you have observed, even though both the lists are different, the permutations of these are same. With the above test, we can conclude that if the contents of the list are same then the permutations are same.
Here goes the algorithm
As we don't know the end we will use while loop so that it will go on till infinity.
  • Lets create a list and name it cubes.
  • For each and every iteration, we will create a sorted list of string of cube of the number[sorted(list(string(i3)))].
  • We wil add that cube to the cubes list.
  • Count the number of times cube is in the cubes list. If it is 5 times, then break the loop and print the cube of first instance of cube in the list.
The program is as follows. And for example, see the Program section

Program

In [ ]:
# http://radiusofcircle.blogspot.com

# import time
import time

# time at the start of program
start = time.time()

# list to store cubes
cubes = []

# iterator
i = 0

# while loop
while True:
 # cube of the number
 cube = sorted(list(str(i**3)))
 # appending the cube to cubes list
 cubes.append(cube)
 # check if it occured 5 times
 if cubes.count(cube) == 5:
  # print the cube of the smallest such cube
  print (cubes.index(cube))**3
  break
 i += 1

# time at the end of program
end = time.time()

# total time taken
print end - start
Lets consider an example.
Assume that, python has already done some iterations and the present value of i = 27
We will see what sorted(list(str(i**3))) does:
In [2]:
# i
i = 27

# str(i**3)
print str(i**3)

# list(str(i**3))
print list(str(i**3))

# sorted(list(str(i**3)))
print sorted(list(str(i**3)))

19683
['1', '9', '6', '8', '3']
['1', '3', '6', '8', '9']
So at any point of time, if there are more than one permutations of 19683(273) are cubes, then sorted(list(str(i**3))) will always return ['1', '3', '6', '8', '9'].
In similar way, we will have sorted list of cubes of numbers(cubes list). As list supports duplicates, none of the duplicated values are erased.
After we've found the cube, we will append the cube to the cubes list.
As the present cube also becomes part of cubes list, we will count if there are 5 such values of cube. If yes we will break the loop, otherwise the loop continues.
You can download the code from Github Gist pep62.py

Output


Summary

This problem, once I have got the solution seems to be very simple. But when I tried solving, I banged my head to get the solution. Actually the mistake was on my side. I was thinking only in one way. i.e. to solve it using the permutations function. But at the end it was actually not necessary. Anyways it is a very simple problem once you will understnd that there is no need for the concepts of permutations. I had fun solving this problem.
If you have any doubts or didn't understand anything, comment in the comment box below and I will be glad to help you.
Please comment if I have made any typo or if you have any feedback. If you have any new program or better program comment in the comment box below. I will be very happy to see your comment.
Let me know about this format of writing.
You can also contact me.
Thank you. Have a nice day.😃
Labels: