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:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more