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 (P_3,127=8128), square (P_4,91=8281), and pentagonal (P_5,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

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:

n² + 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:
n²+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

Answer: 28684
Execution time: 0.026999995 seconds
Output:

Project Euler Problem 61 output

Project Euler Problem 61 with answer

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

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