오일러 프로젝트 44 번 문제는 두 오각수의 합과 차이가 모두 오각수가 되는 두 오각수의 쌍 중에서 가장 가까운 두 수의 거리를 찾는 문제이다. 간단히 요약하니까 무슨말인지 알아듣기 어려운데, 문제는 아래와 같으며 의외로 어렵지 않다.
오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다. 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, … 위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다. 합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=44)
접근
오각수의 일반항인 Pn은 n에 대한 이차식의 모양을 하고 있다. 따라서 n 이 커지면 커질 수록 
문제는 이 값이 언제쯤 나타날 것인지에 대한 정보는 직접적으로 주어지지 않았다는 점이다. 따라서 특정한 크기의 오각수 집합을 미리 만들어 놓고 사용할 수는 없다.
따라서 다음과 같은 알고리듬으로 진행한다.
- 조건을 만족하지 못하는 정렬된 오각수의 리스트가 있다고 가정한다. (k = 1, 2, 3, … n – 1)
- 1.의 리스트의 가장 큰 오각수 바로 다음 번 오각수 Pn을 생성한다.
- 두 오각수의 합이 Pn이 된다고 가정하면, 1.의 리스트 중 p와 s의 합이 Pn이 될 것이다. (p + s == Pn)
- 따라서 1.의 리스트에서 임의의 원소 p를 뽑고, s = Pn – p 로 계산한다. 만약 s가 1.의 원소라면 합의 조건은 만족한다.
- 두 오각수 p, s에 대해서 차이인 d를 계산한다. 같은 방식으로 1.의 리스트에 d가 포함된다면 모든 조건이 만족된다.
따라서 새로 추가되는 오각수가 Pj , Pi 라는 점에 방점을 찍지 않고 이전 시행에서 만들어진 연속 오각수 리스트로부터 답을 찾을 수 있는지를 검사한다. 조금 돌아가는 느낌이기는 하지만, 아주 빠르게 답을 찾을 수 있다.
참고로 리스트를 통해서 “정렬된” 오각수 리스트를 관리하면서, 동시에 순서없는 집합을 이용해서 오각수여부 판별을 빠르게 처리하는 것이 성능 개선의 팁이라 할 수 있다.
def make_pent(k):
return k * (k * 3 - 1) // 2
def main():
pents = [make_pent(x) for x in range(1, 4)]
sieve = set(pends)
k = 4
while True:
pn = make_pent(k)
for p in pents:
s = pn - p
d = abs(p - s)
## s와 p의 합이 오각수(pn)이려면, s도 오각수여야
## 하고, 두 수의 차인 d 역시 오각수여야 한다.
if s in sieve and d in sieve:
print(d)
return
## 새로운 pn을 오각수 집합에 추가하고, 다음 오각수를 향해서 진행
pents.append(pn)
sieve.add(pn)
k += 1
%time main()
## 실행시간 1초 미만Swift 풀이
Swift 코드 역시 대동소이하다.
fun make_penta(_ k: Int) -> Int = { return k * (k * 3 - 1) / }
main: do {
var a = (1...3).map(make_penta)
var b = Set(a)
var k = 4
while true {
let pn = make_penta(k)
for p in a {
if case let s = pn - p, case let d = abs(s - p),
b.contains(s), b.contains(d) {
print(d)
break main
}
}
a.append(pn); b.insert(pn)
k += 1
}
}