오일러 프로젝트 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 = 40775가 됩니다. 오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요.

http://euler.synap.co.kr/prob_detail.php?id=45

접근

언뜻 보기에 이 문제는 별로 어려운 게 아닌 것 같다. k를 늘려나가면서 삼각수를 구하고, 이 삼각수가 오각수이면서 육각수인지를 판단하면 된다. 어떤 수가 오각수이거나 육각수인지를 판단하려면, 해당 수열의 일반항의 식을 거꾸로 푼 식에 대입한 후 그 결과가 정수로 떨어지는지를 보면 된다.

우선 문제의 주어진 예시를 잘 보면, 모든 육각수가 삼각수 수열에 등장하는 것처럼 보인다. 삼각수 공식에 n 대신, 2k – 1을 넣어서 정리해보면…

\begin{array}{lll}
T_{2k-1} &= frac{(2k-1)(2k)}{2}  &left(k = 1, 2, 3,...right) \\
&=k(2k-1)
\end{array}

육각수의 일반항 공식과 같아진다. 즉 모든 홀수번째 삼각수는 육각수라는 점을 알 수 있다. 따라서 오각수인 육각수를 찾으면 되는데, 이차항의 계수가 오각수 공식에서 3으로 더 크기 때문에, 거꾸로 육각수인 오각수를 찾는 편이 더 빠르게 찾을 수 있다.

%%time

def p(k=1):
    while True:
        yield k * ( 3 * k - 1) // 2
        k += 1


def test(h):
    k = ((8 * h + 1) ** .5 + 1) / 4
    return int(k) == k

g = p(166)
while True:
    pk = next(g)
    if test(pk):
        print(pk)
        break

참고로, 육각수 검사 공식은 다음과 같이 유도된다. 위 코드에서는 아래 식으로 구한 순번 k가 정수인지 판단하는 것으로 h가 오각수인지를 판단한다.

\begin{array}{lll}
H_n &= n(2n - 1) \\
&= 2(n^2 - n + \frac{1}{16}) - \frac{1}{8} \\
&=2(n - \frac{1}{4})^2 - \frac{1}{8} \\
\frac{1}{2}\left(H_n + \frac{1}{8}\right) &= (n - \frac{1}{4})^2 \\
n &=  \sqrt{\frac{1}{2}\left(H_n + \frac{1}{8}\right)} + \frac{1}{4} \\
&= \frac{1}{4}\left(\sqrt{8H_n + 1} + 1\right)
\end{array}