project euler 44

오일러 프로젝트 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

“가장 작은”에 착안하여 오각수 집합의 규모를 늘려가면서 조건을 만족하는 가장 작은 오각수를 찾으면 된다. 오각수의 일반항 식은 이차식으로 k 가 크면 클 수록 다른 오각수와의 차도 커지기 때문이다.

서너 개의 오각수로부터 다음 오각수를 만들고, 이미 만들어진 오각수를 새 오각수에서 뺀 차가 기존 오각수에 있는지를 검사한다. 만들어진 오각수는 집합에 추가하고 다음 오각수를 판별하는 방법을 진행하면 된다.

def toPentagonal(n):
    p = n * (3 * n - 1) // 2
    return p

def e44():
    ps = [toPentagonal(n) for n in range(1, 3)]
    k = 3
    while True:
        pn = toPentagonal(k)
        ts = set(ps)
        for x in ps[::-1]:
            y = pn - x
            if y in ts:
                d = abs(x-y)
                if d in ts:
                    print(d)
                    return
        ps.append(pn)
        k += 1



%time e44()

# 5482660
# Wall time: 790 ms