프로젝트 오일러 045

문제

45번 문제

오각수와 육각수도 되는, 40755 다음으로 큰 삼각수는?

사이냅소프트

삼각수와 육각수

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

여기서 사소한 선택을 하나 해야 합니다.

1. 오각수의 수열을 진행하며 육각수인지 검사
2. 육각수의 수열을 진행하며 오각수인지 검사

각 수열의 일반항에서 최고차항은 둘 다 2차항인데, 오각수의 최고차항 계수가 더 큰 값이므로 오각수를 기준으로 육각수인지 검사하는 것이 좀 더 (사실 비율로는 훨씬 더) 빠를 겁니다.

육각수인지 검사하는 것은 Hn에 관한 식을 반대로 n에 관한 식으로 풀어낸 후 Hn 자리에 어떤 값을 넣어서 그 값이 정수인지 확인하면 됩니다.

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())