-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathp044.py
84 lines (66 loc) · 3.09 KB
/
p044.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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
# Steve Beal
# Project Euler problem 44 solution
# 8/14/15
# Pentagonal numbers are generated by the formula, P_n = n(3n-1)/2. The first
# ten pentagonal numbers are: 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
# It can be seen that P_4 + P_7 = 22+70 = 92 = P_8. However, their difference,
# 70-22 = 48, is not pentagonal.
# Find the pair of pentagonal numbers, P_j and P_k, for which their sum and
# difference are pentagonal and D = | P_k - P_j | is minimized; what is the value of D?
# 1 | 5 | 12 | 22 | 35 | 51 | 70 | 92 |
# 1 0 | 4 | 11 | 21 | 34 | 50 | 69 | 91 |
# 5 | 0 | 7 | 17 | 30 | 46 | 65 | 87 |
# 12 | | 0 | 10 | 23 | 39 | 58 | 80 |
# 22 | | | 0 | 13 | 29 | 48 | 70 |
# 35 | | | | 0 | 16 | 35 | 57 |
# 51 | | | | | 0 | 19 | 41 |
# 70 | | | | | | 0 | 22 |
# 92 | | | | | | | 0 |
from utils import pentagonal_gen, is_pentagonal
def smallest_double_pent_diff():
p = pentagonal_gen()
min_diff = None
pents = []
inc = 100
abs_i = 1
while True:
for _ in range(inc):
pents.append(next(p))
# the min value above the 0 diagonal
for i in range(abs_i, len(pents)):
# print(i)
for j in range(1, i+1):
# get the difference
pj, pk = pents[i-j], pents[i]
_sum = pj+pk
_diff = pk-pj
# if j is 1, we're on the diagonal above 0 in column i.
# this means that we've checked everything smaller already,
# which is to the left, and we've either not found a suitable
# pair, or we have and we need to ensure that no other pair is
# smaller, since the diagonals can be smaller than some vals
# to the left.
if j == 1:
min_diag = _diff
# if we have a min_diff, don't check any that are greater, duh.
if min_diff and _diff > min_diff:
break
# check if both sum and diff are pentagonal
pent_pos = is_pentagonal(_sum)
pent_neg = is_pentagonal(_diff)
# if they're both pentagonal, get the diff.
# if this is our first actual valid diff, or it's smaller than
# the current one, set it to be the min.
if pent_pos and pent_neg:
if not min_diff or _diff < min_diff:
min_diff = _diff
# if we have a min diff and it's less than the min diag value,
# there can be nothing smaller above or to the right, so stop
if min_diff and min_diff <= min_diag:
return min_diff
# this counts the beginning index of each "chunk" that we have to add
# to pents[] (in case we don't find stop in the first chunk) so that
# we don't recalculate all the smaller values we've already tried
abs_i += inc
# if abs_i > 100: break
print(smallest_double_pent_diff())