Loading...
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.
- 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 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.
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.
Posted by Wolfgang Büchel | December 18, 2018, 11:40 PMsuch elegant solution!
Posted by Judy | June 17, 2017, 8:43 PMThis 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 PMThanks for your comment and I’m really glad it helped you.
Posted by Mike Molony | January 17, 2016, 1:58 PMMy 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