프로젝트 오일러 044

오각수의 차이

합과 차가 모두 오각수인 오각수를 찾는 문제입니다. 특히 그 차이가 최소가 되는 경우를 찾아야 합니다. 두 오각수의 차이의 양상을 알아보기 위해, n번째 오각수를 P(n)으로 표기하기로 하고, P(n), P(n - k)의 차이를 보면 $k(6n+1-3k)/2$가 됩니다. 즉 n이 작을수록, 그리고 작은 n에 대해서 순번의 차이인 k가 작을수록 두 오각수의 차이가 작을 것으로 생각됩니다.

탐색

임의의 자연수 n과 n보다 작은 자연수 m에 대해서 P(n) + P(m), P(n) - P(m)이 모두 오각수인지를 검사하고, 이런 경우가 없으면 n을 1씩 늘려가면서 다시 그보다 작은 m에 대해서 검사하는 방식으로 값을 찾을 수 있습니다. 이 과정을 반복하다가 첫번째로 발견하는 P(m), P(n)은 조건을 만족하면서 그 차가 가장 작은 m, n의 쌍이 됩니다.

오각수의 일반항 공식을 역으로 정리하고, 해당 식의 값이 자연수라면 그 수가 오각수인것으로 판별할 수 있습니다.

def ispenta(p):
    n = ((24 * p + 1)**0.5 + 1) / 6
    return n == int(n)


def main2():
    n = 2
    while True:
        k = n * ( 3 * n - 1) // 2
        for m in range(n - 1, 0, -1):
            j = m * (3 * m - 1) // 2
            if ispenta(j + k) and ispenta(k - j):
                print(k -j)
                return
        n += 1