Problem #61 involves the figurate numbers. The question reads:
Project Euler Problem 61: 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.
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 (P3,127=8128), square (P4,91=8281), and pentagonal (P5,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.
This is one of the problems that horrified me for years of doing Project Euler problems because I really didn’t want to implement a solution to it. My solution definitely falls into the category of brute force, but it does run quite fast so I believe it is acceptable. Here is my solution:
Solution #1: Brute Force Approach
We simply list all of the triangular, square, pentagonal, hexagonal, heptagonal, and octagonal numbers less than 10000. Next we iterate through all of the octagonal starting numbers and find all of the figurate numbers which start with the last two digits of the corresponding octagonal. For each 1st figurate number, we list all 2nd figurate numbers with the same digits. We do this five times until we have obtained a 6-tuple of figurate numbers. Finally, we check all 6-tuples obtained in this process and store the maximum total of the 6-tuples that satisfy the property. Like I said, this solution was meant solely to solve the problem no matter the cost, so it is far from elegant. Here is an implementation of it in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #61
'''
import time
def projectEulerProblemSixtyOne():
triangles = []
c = 2
v = 1
while(v<10000):
if(v>=1000):
triangles.append(v)
v+=c
c+=1
squares = []
c = 32
v = c*c
while(v<10000):
squares.append(v)
c+=1
v += (2*c-1)
pentagons = []
c = 2
v = 1
while(v<10000):
if(v>=1000):
pentagons.append(v)
v+=(3*c-2)
c+=1
hexagons = []
c = 2
v = 1
while(v<10000):
if(v>=1000):
hexagons.append(v)
v+=(4*c-3)
c+=1
heptagons = []
c = 2
v = 1
while(v<10000):
if(v>=1000):
heptagons.append(v)
v+=(5*c-4)
c+=1
octagons = []
c = 2
v = 1
while(v<10000):
if(v>=1000):
octagons.append(v)
v+=(6*c-5)
c+=1
total = triangles[:]
for x in squares:
if x not in total:
total.append(x)
for x in pentagons:
if x not in total:
total.append(x)
for x in hexagons:
if x not in total:
total.append(x)
for x in heptagons:
if x not in total:
total.append(x)
for x in octagons:
if x not in total:
total.append(x)
possibleTuples = []
for o in octagons:
a = o%100
p1 = []
for x in total:
if(x/100==a):
p1.append(x)
for o1 in p1:
b = o1%100
p2 = []
for x in total:
if(x/100==b):
p2.append(x)
for o2 in p2:
c = o2%100
p3 = []
for x in total:
if(x/100==c):
p3.append(x)
for o3 in p3:
d = o3%100
p4 = []
for x in total:
if(x/100==d):
p4.append(x)
for o4 in p4:
e = o4%100
p5 = []
for x in total:
if(x/100==e and x%100 == o/100):
p5.append(x)
for o5 in p5:
possibleTuples.append([o,o1,o2,o3,o4,o5])
realPossible = []
for a in possibleTuples:
whole = []
hpRep = False
heRep = False
peRep = False
sqRep = False
trRep = False
repeat = False
for x in a:
if x not in whole:
whole.append(x)
else:
repeat = True
break
if(x in hexagons):
heRep = True
elif(x in triangles):
trRep = True
elif(x in heptagons):
hpRep = True
elif(x in pentagons):
peRep = True
elif(x in squares):
sqRep = True
if(hpRep and heRep and peRep and sqRep and trRep and not repeat):
realPossible.append(a)
maxFound = -1
for x in realPossible:
t = 0
for y in x:
t+=y
if(t>maxFound):
maxFound = t
return maxFound
start = time.time()
print projectEulerProblemSixtyOne()
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
28684
--- 0.0513989925385 seconds ---
for given problem.
'''
And with that, we’re done. 150 lines of code for a program that runs in a 20th of a second. Like I said in the intro, I dreaded solving this problem because it seemed like a pain to implement. I hope you can understand the messy solution I made.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 