프로젝트 오일러 045

삼각수와 육각수

삼각수 공식에서 n을 (2k - 1)로 치환하여 정리하면 k에 관한 육각수 공식이 됩니다. 즉, 2k - 1은 홀수를 나타내는 식이니, 홀수번째 삼각수는 육각수이기도 한 것이죠. 따라서 모든 육각수는 삼각수입니다. 그렇다면 오각수와 육각수의 교집합에서 탐색하면 됩니다. 40,775보다 큰 오각수이면서 육각수인 수를 찾으면 되는 것이죠.

이 때 탐색 방식에는 두 가지가 있습니다. 오각수의 수열을 따라 만들어나가면서 육각수인지 검사하거나, 반대로 육각수의 수열을 따라 만들어 나가면서 오각수인지를 검사합니다. 일반항을 계산하는 식에서는 두 식의 차수는 같지만, 오각수 공식이 최고차항 계수가 더 크므로 답까지의 반복 횟수는 오각수를 기준으로 하는 것이 더 적은 시도를 통해서 답을 구하게 됩니다.

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

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

def main():
    g = p(166)
    while True:
        pk = next(g)
        if test(pk):
            return pk


if __name__ == '__main__':
    print(main())