061.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

#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.

   #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 (P3,127=8128), square (P4,91=8281), and pentagonal (P5,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.

#Answer:
	#28684

from time import time; t=time()
from itertools import permutations

flags = [{},{},{},{},{},{}]
def setflag(k, n):
    u, v = n//100, n%100
    if v < 10: return
    flags[k].setdefault(u, [])
    flags[k][u].append(v)
for i in range(45, 141):
    setflag(0, i*(i+1)//2)
for i in range(32, 100):
    setflag(1, i*i)
for i in range(26, 82):
    setflag(2, i*(3*i-1)//2)
for i in range(23, 71):
    setflag(3, i*(2*i-1))
for i in range(21, 64):
    setflag(4, i*(5*i-3)//2)
for i in range(19, 59):
    setflag(5, i*(3*i-2))

def find_next(key, level, f):
    keys = flags[level].get(key, [])
    if not keys: return []
    if level == f[-1]:
        return [[key, l] for l in keys]
    rets = []
    for newkey in keys:
        rets += [[key]+l for l in find_next(newkey, f[f.index(level)+1], f)]
    return rets
    
for key in flags[0]:
    for f in permutations(range(1, 6)):
        rets = find_next(key, 0, (0,)+f)
        for ret in rets:
            if ret[-1] == key:
                nums = [ret[i]*100+ret[i+1] for i in range(5)]
                nums.append(ret[5]*100+ret[0])
                print(sum(nums))#, time()-t, nums, f
                import sys;sys.exit()