Project Euler 61: Find the sum of the only set of six 4digit figurate numbers with a cyclic property.
Problem Description
Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
Triangle  P(_{3,n})=n(n+1)/2  1, 3, 6, 10, 15, …  
Square  P(_{4,n})=n^{2})  1, 4, 9, 16, 25, …  
Pentagonal  P(_{5,n})=n(3n−1)/2  1, 5, 12, 22, 35, …  
Hexagonal  P(_{6,n})=n(2n−1)  1, 6, 15, 28, 45, …  
Heptagonal  P(_{7,n})=n(5n−3)/2  1, 7, 18, 34, 55, …  
Octagonal  P(_{8,n})=n(3n−2)  1, 8, 21, 40, 65, … 
The ordered set of three 4digit numbers: 8128, 2882, 8281, has three interesting properties.
 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).
 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.
 This is the only set of 4digit numbers with this property.
Find the sum of the only ordered set of six cyclic 4digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
Analysis
Straightforward bruteforce solution in three easy steps:
1. Generate each polygonal number with it’s type as a tuple.
2. Build a dictionary (hash) of each tuple to every other tuple not of the same type that follows the criteria of the problem (ending two digits matching the beginning two digits). Here’s a sample of the relation:
{(3, 1035): [(7, 3553), (5, 3577)]
(3, 1081): [(6, 8128), (5, 8177)]
(3, 1128): [(8, 2821), (7, 2839), (6, 2850), (5, 2882)]
(3, 1176): [(6, 7626)]
(3, 1225): [(7, 2512), (6, 2556)]
Here’s the full set (study61.txt) of all 293 relations.
3. Run through the dictionary and find every six member family that follows the criteria.
3a. Make sure the last two digits of the last number match the first two digits of the first number.
Project Euler 61 Solution
Runs < 0.040 seconds in Python 2.7.Use this link to get the Project Euler 61 Solution Python 2.7 source.
Afterthoughts

No afterthoughts yet.
Very elegant, simple solution. Great.
I generalized the problem: Find every solution for all (i.e. more) types of polygonal numbers (not only 3 to 8, say 3 to 20).
So I found, your prog can be improved: It’s not necessary to iterate over the whole
dict ds (in doing so, you find every solution several times). It’s sufficient to iterate over the type with the greatest number (in your prog type = 8).
Running time for maxtype=12:
0.16 sec vs. 1.88 sec.
such elegant solution!
This is a great example to learn about data structures in Python such as lists,dictionaries and tuples..I have recently started solving Project Euler problems to learn Python better and this is the most sophisticated Python solution I have seen so far!
Learnt a lot from it. Kudos to you.
Thanks for your comment and I’m really glad it helped you.
My solution
Reasonable fast solution of Project Euler problem 61 (under 3 ms)
http://www.daniweb.com/code/snippet344678.html