// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 61 Solution

Project Euler 61 Solution

Project Euler 61: Find the sum of the only set of six 4-digit 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)=n2)   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 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.

Analysis

Straight-forward brute-force 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*n-1)/2), (6,n*(2*n-1)), (7,n*(5*n-3)/2), (8,n*(3*n-2))
 
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])
download arrowUse 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.
|28684|

Afterthoughts

    No afterthoughts yet.
Project Euler 61 Solution last updated

Discussion

4 Responses to “Project Euler 61 Solution”

  1. such elegant solution!

    Posted by Judy | June 17, 2017, 8:43 PM
  2. 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.

    Posted by Orchisama | January 17, 2016, 12:11 PM
  3. My solution

    Reasonable fast solution of Project Euler problem 61 (under 3 ms)
    http://www.daniweb.com/code/snippet344678.html

    Posted by Tony Veijalainen | February 20, 2011, 5:45 PM

Post a comment