삼각수, 오각수, 육각수는 각각 아래 식으로 구할 수 있습니다.
- 삼각수 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}