오일러 프로젝트 45

오일러 프로젝트 45 번은 삼각수이면서, 오각수이고 동시에 육각수인 수를 찾는 문제이다.

삼각수, 오각수, 육각수는 아래 식으로 구할 수 있습니다.
 

삼각수 Tn = n (n + 1) / 2 1, 3, 6, 10, 15, …

오각수 Pn = n (3n − 1) / 2 1, 5, 12, 22, 35, …

육각수 Hn = n (2n − 1) 1, 6, 15, 28, 45, …

 
여기서 T285 = P165 = H143 = 40755 가 됩니다. 오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요.
http://euler.synap.co.kr/prob_detail.php?id=45

접근

이 문제는 그리 어렵지 않아 보인다. 왜냐하면 각 수의 일반항은 모두 간단한 2차식으로 표현되며,  체크만 잘하면 될 것 같기 때문이다. 하지만 실제로 너무 나이브하게 접근했다가는, 경악스러운 수준의 실행 시간을 맛볼 수 있다.
이렇게 접근해보자. 홀수 번째 삼각수 는 다음과 같이 정리된다.

그리고 그 모양은 육각수의 일반항 식으로 귀결된다.  즉 모든 홀수 번째 삼각수는 항상 육각수이므로, 반대로 모든 육각수는 삼각수이다. 따라서 이 조건에 의해서 오각수가 육각수인지만 판별해나가면 된다. 육각수 판별식은 육각수 일반항 식을 역으로 풀어서 n이 자연수인지 판단한다.

파이썬 풀이

def is_hexagonal(k):
    n = (((8*k+1) ** 0.5) + 1 ) /4
    return int(n) == n
def pn(n):
    return n * ( 3 * n - 1) // 2
def e45():
    k = 166
    while True:
        pk = pn(k)
        if is_hexagonal(pk):
            print(pk)
            break
        k += 1
%time e45()
# Wall time: 98 ms