-
-
Notifications
You must be signed in to change notification settings - Fork 45.9k
/
sol1.py
49 lines (40 loc) · 1.46 KB
/
sol1.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
"""
Problem 44: https://projecteuler.net/problem=44
Pentagonal numbers are generated by the formula, Pn=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 P4 + P7 = 22 + 70 = 92 = P8. However, their difference,
70 - 22 = 48, is not pentagonal.
Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference
are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?
"""
def is_pentagonal(n: int) -> bool:
"""
Returns True if n is pentagonal, False otherwise.
>>> is_pentagonal(330)
True
>>> is_pentagonal(7683)
False
>>> is_pentagonal(2380)
True
"""
root = (1 + 24 * n) ** 0.5
return ((1 + root) / 6) % 1 == 0
def solution(limit: int = 5000) -> int:
"""
Returns the minimum difference of two pentagonal numbers P1 and P2 such that
P1 + P2 is pentagonal and P2 - P1 is pentagonal.
>>> solution(5000)
5482660
"""
pentagonal_nums = [(i * (3 * i - 1)) // 2 for i in range(1, limit)]
for i, pentagonal_i in enumerate(pentagonal_nums):
for j in range(i, len(pentagonal_nums)):
pentagonal_j = pentagonal_nums[j]
a = pentagonal_i + pentagonal_j
b = pentagonal_j - pentagonal_i
if is_pentagonal(a) and is_pentagonal(b):
return b
return -1
if __name__ == "__main__":
print(f"{solution() = }")