-
Notifications
You must be signed in to change notification settings - Fork 0
/
euler061.py
61 lines (49 loc) · 2.62 KB
/
euler061.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from itertools import permutations
upper_bound = 500
limit = lambda x : x > 999 and x < 10000 and '0' not in str(x)
polygonals = [filter(limit, [n*(3*n - 2) for n in xrange(upper_bound)]),
filter(limit, [n*(5*n - 3)/2 for n in xrange(upper_bound)]),
filter(limit, [n*(2*n - 1) for n in xrange(upper_bound)]),
filter(limit, [n*(3*n - 1)/2 for n in xrange(upper_bound)]),
filter(limit, [n*n for n in xrange(upper_bound)]),
filter(limit, [n*(n + 1)/2 for n in xrange(upper_bound)])]
def find_partial_cycle(poly_lists, cycle):
if len(poly_lists) == 0: return cycle
polys, poly_lists = poly_lists[0], poly_lists[1:]
for x in polys:
if len(cycle) == 0 or cycle[-1] % 100 == x / 100:
new_cycle = find_partial_cycle(poly_lists, cycle[:] + [x])
if len(new_cycle) - len(cycle) == len(poly_lists) + 1 and \
(len(poly_lists) != 0 or \
new_cycle[0] / 100 == new_cycle[-1] % 100):
return new_cycle
return cycle
def find_cycle(poly_lists):
cycle = find_partial_cycle(poly_lists, [])
if len(cycle) > 0 and cycle[-1] % 100 == cycle[0] / 100: return cycle
return []
def euler61():
"""http://projecteuler.net/index.php?section=problems&id=61
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=n^2 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."""
for perm in permutations(polygonals):
cycle = find_cycle(list(perm))
if len(cycle) == 6:
return sum(cycle)