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.def fn(n):
return (3,n*(n+1)/2), (4,n*n), (5,n*(3*n1)/2), (6,n*(2*n1)), (7,n*(5*n3)/2), (8,n*(3*n2))
def next(types, data):
if len(types) == 6 and data[0] // 100 == data[1] % 100:
print data, sum(data)
else:
for t, n in ds.get((types[1], data[1]), []):
if t not in types:
next(types+[t], data+[n])
p = [] # build a list of polygonal numbers with their type (type, pnum)
n = 19 # first n for octogonal number > 999
while n < 141: # last n for triangle numbers < 10000
for type, data in fn(n):
if 1000 <= data <= 9999 and data % 100 > 9:
p.append( (type, data) )
n+=1
ds = {} # build a dictionary of tuples
for t1, d1 in p:
for t2, d2 in p:
if t1 != t2 and d1 % 100 == d2 // 100:
ds[t1, d1] = ds.get((t1, d1),[]) + [(t2, d2)]
print "Project Euler 61 Solution Set"
for type, data in ds: next([type], [data])
Use this link to get the Project Euler 61 Solution Python 2.7 source.Answer
Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.Afterthoughts

No afterthoughts yet.
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