Skip to main content

Problem 61 Project Euler Solution with python

Cyclical figurate numbers

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
Square P4,n=n2 1, 4, 9, 16, 25, ...
Pentagonal P5,n=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal P6,n=n(2n−1) 1, 6, 15, 28, 45, ...
Heptagonal P7,n=n(5n−3)/2 1, 7, 18, 34, 55, ...
Octagonal P8,n=n(3n−2) 1, 8, 21, 40, 65, ...
The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
  1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
  2. Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), is represented by a different number in the set.
  3. This is the only set of 4-digit numbers with this property.
Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.



 
 This problem is fairly simple but restraining ourselves from using the same polygon numbers again and again is little difficult.

Okay lets first understand the pre-requisities  before we delve deep into the algorithm.

Now this problem is something similar to "Circular permutations". Because the numbers are cyclic and there are 6 numbers that are to be arranged the number of possibilities we have is:
(6-1)! = 5! = 120.

You can learn more about Circular Permutations from here:
Tutors 4 You Circular Permutations
Circular Permutations - Wolfram Math
Circular Permutations - askIITans

Even though all these permutations are not possible, but let us first consider the ways in which the numbers can be arranged. Some of them are:
Permutations of different Figurates
Permutations of different Figurates
Of course all of these are not possible, but only one of these permutations is possible. But how can we get to know the correct permutation for our solution.

There is no option for us but to iterate through all the permutations until we arrive at our solution. So the algorithm is as follows:


As the permutations are cyclic we will consider that our first number is Octagonal number. Assuming in this way doesn't make any difference, because if the same number were to be the second element, even then the element following the octagonal number will be the same. Irrespective of the position of the octagonal number the number following the octagonal number will be the same. 


You can start with any of the polygonal numbers. But the reason for me to start with the Octagonal numbers is that it has only a few elements and thus we can improve the performance.

Now for the generation of the corresponding 4 digit figurate numbers we have to go back to Quadratic Equations concepts. 

We will have to do some math to find out the bounds in which we can generate 4 digit numbers for the corresponding Figurate numbers.

I will give you one example.

To find the starting value let us first equate the quadratic expression to 999, then we will get the following quadratic equation:

n2 + n - 1998 = 0
On solving the above equation for n and rounding off the value of n we will get n = 45.

Similarly for the upper bound we will equate the quadratic expression to 10000, then we will get the following quadratic equation:
n2+n-20000 = 0

On solving the above equation for the value of n we will get n = 141.

So the domain in which the triangular numbers will be 4 digits will be [45, 140].

You can apply the similar technique for all the other Figurate numbers and you will get the following:

Square Numbers - [32, 99]
Pentagonal Numbers - [26, 81]
Hexagonal Numbers - [23, 70]
Heptagonal Numbers - [21, 63]
Octagonal Numbers - [19, 59]

You can learn about Quadratic Equations from the following:
Quadratic Equations - Math is fun
Quadratic Equations - Wiki
Quadratic Equation - Wolfram math
Solving Quadratic Equations - Purple Math

So again, we will assume that the first number in our list will be Octagonal number, then the remaining polygons are : Heptagonal Numbers, Hexagonal Numbers, Pentagonal Numbers, Square Numbers, Triangular Numbers. Let us call the collection of these things as tsphh(Triangular, Square, Pentagonal, Hexagonal, Heptagonal)

Lets start with our iterations. Please bear with me because we will make a lot of nested iterations. If you are not able to digest this one, then I would suggest you to translate the algorithm line by line into a program and then see the output for yourself. Or for that matter you can also plugin values instead of the variables and you will for sure understand, whats happening.

We will create all the 4 digit triangular numbers, square numbers, pentagonal numbers, hexagonal numbers, heptagonal numbers, octagonal numbers.

First we will start iterating through the octagonal numbers. The iterator is n1(Number 1 in our list).

Then we will iterate through tsphh and let the iterator be polygon 2(This will become the second polygon because the first polygon is Octagonal).

With polygon 2 already in hand, we will iterate through this polygon to get number n2(Second number in our list).

We will check if the last two digits of n1 is equal to first two digits of n2, if the condition is satisfied then we can dig deeper otherwise go for next iteration.

With the condition satisfied we will choose another polygon from the list of tsphh and lets call it polygon3. Remember that polygon3 should not be equal to polygon2

We will start iterating through polygon3 to generate the number n3(Third number in our list). 

Now this number should satisfy the condition - Last two digits of number n2 should be equal to first two digits of newly generated number n3. If the condition is not satisfied continue with the next iteration.

In the similar way we will generate polygon4 which on iteration will give n4. Be careful that polygon4 is not equal to polygon3 and also not equal to polygon2.

Check for the condition - Last two digits of number n3 should be equal to first two digits of number n4. Again if the condition is not satisfied continue with the next iteration.

Go ahead and generate polygon5 with numbers n5. Again polygon5 should not be equal to any of the polygon2, polygon3, polygon4.

Check for the condition - Last two digits of n4 should be equal to n5.

With the above condition satisfied we will generate polygon6 with numbers n6. Here the condition for polygon6 is that it should not be equal to any of the polygon2, polygon3, polygon4, polygon5.

This time we will have to check for the condition - Last two digits of n5 is equal to First two digits of n6 and also the Last two digits of n6 should be equal to First two digits of n1(The condition for all the numbers being cyclic).

At this point, if the last condition is satisfied you will only be left out with one set of n1, n2, n3, n4, n5, n6 and this is the answer.  

Now have a look at the program and you will for sure understand everything easily.

Program

The program is fairly easy if you have already read the algorithm part above. But for your convenience I will just touch up the code.

Line 10 - 25: We are generating the Figurate Numbers which are required for calculations. Using the quadratic equations I was able to conclude the range. Also I have added 1 to the upper limit, because xrange will only generate numbers upto a number less than the given number. See about xrange on python docs.

Line 27- 47: I have broken the numbers generated in the above step to tuples with 2-2 digits so that we can calculate easily. You can also combine line 10-25 with this step, but for the reason of reducing the complexity I have added these lines.

Line 50 - 54: The function find_sum will take tuples and convert them back to their original numbers and give the summation of all such tuples. Try plugging in some values. Input of this function is a list of tuples.

Line 56-94: This is the core concept of the program and I have discussed this section in a detailed fashion in the algorithm section.

As always you can download the above code from Github Gist pep61.py

Output


Summary

After I have solved this problem, I thought it was fairly simple. But to get the solution for this problem, it took some time for me. This problem is simple when compared to some other problems which we have solved in the past. Anyways I had fun solving this problem. I am satisfied with the program execution time. But the execution time you are seeing is the execution time after I have added comments to the program. Recently I have observed that when we add comments to the program the execution time increases, but the inverse happens when a person reads the code. I preferred adding comments even if the time of execution increases, because readability of the code is most important. Also I was not able to adhere to pep 8. At the end I think we can improve in terms of following pep8 standards.

By the way, the cyclic chain formed in the above problem can be given as follows:

Cyclic chain for the problem 61 project euler
Cyclic chain for the problem 61 project euler
As always if you have any doubt or haven't understood anything comment in the comment box below and I will glad to help you.

Please comment in the comment box if you have found any bug or have any suggestion or if you have a different program or if you have a better program. I will be very happy to see that comment.

You can also contact me.

Thank you. Have a nice day.😃

Popular posts from this blog

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...

Add/Embed SVG to Blogger website

In this post I will tell you my method(trick) of adding SVG images in a blogger website or blog. Before starting , the first thin g I am assu m ing is that you are aware of SVG if you are here. If not please see S calable V ec tor G raphics Recently when I tried to embed a SVG image for a post on pygal, I tried uploading the SVG file and blogger Image uploader came up with an error, because of which I had to find some other way.  SVG File upload Error in Blogger  I started sea rc hing Google " Embed SVG in Blogger " . I found blogorrhea , w h ich gave some i nformatio n on add ing SVG directly as a markup , which worked , but I faced another problem using this . Also th is guy has used lot of Javascript which was confusin g for me, being new to using SVG.   So I first t houg ht of learning on h ow to embed SVG in HTML and t his on e worked out. Actually we can embed SVG in HTML i n following ways: Using Object tag Using Iframe tag Using embed...

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 documenta...