책 이야기

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880⋯, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

자연수의 제곱근이 정수가 아니면, 무리수가 된다. 이러한 제곱근의 소숫점은 반복되지 않으면서 무한하게 확장된다.

2의 제곱근은 1.41421356237309504880⋯이며, 소숫점 처음 100자리 숫자의 합은 475이다. 

100까지 자연수 중에서 제곱근이 무리수인 숫자의 소숫점 처음 100자리 숫자의 총합은 얼마인가?

--------------------------------------------------------------------------

처음에는 연분수 문제(문제 64)를 응용해서 간단하게 해결하려 했는데, 제곱근을 직접 계산하지 않으면 소숫점 이하에서 오차가 발생하는 문제가 있어, 제곱근을 손으로 계산하는 방법을 찾아 알고리즘으로 구현했다.

위 링크의 방법2에 왠만한 설명보다 자세하게 나와있기 때문에 코딩하는 데 그리 어렵지 않을 것이다. 프로그램으로 만드는 과정에서 break를 뺀다든지 하는 몇가지 오류가 있어 수정하는 데 시간은 좀 걸렸지만 재미있게 해결 가능한 문제였다.

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

10을 소수의 합으로 나타내는 데에는 다음과 같이 5가지 방법이 있다:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

소수의 합으로 5천가지 이상의 방법으로 표현 가능한 첫 숫자는 무엇인가?

--------------------------------------------------------------------------

31번 문제, 76번 문제를 조금 변형시켜 만들어진 문제이지만, 슬프게도 31번 문제, 76번 문제를 해결하는데 사용한 방법을 적용할 수 없었다. 31번 문제는 동전 숫자를 알아서 반복문을 중첩시켜 해결했고, 76번 문제는 정수론에 있는 분할수 공식을 이용해서 구했는데 이 두가지와는 성격이 달라 그대로 적용할 수 없었다.

영문 위키 Partition(Number Theory) 항목의 Restrcted partition을 잘 이해하면 적용 가능할 것 같은데 이제는 중학교 수준 이하의 실력을 가진 상황에 그 부분을 이해하고 프로그래밍 하는 것이 쉽지 않았다.

그래서, 31번, 76번 문제 모두에 적용가능했던 동적 프로그래밍 방법을 가져와 소수에 맞게 조금 응용해서 해결했다. 정답을 맞췄지만 내 것으로 소화한 것이 아니어서 찝찝함이 남는다.

It is possible to write five as a sum in exactly six different ways:

    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

합계로 5를 나타내는 방법은 다음과 같이 6가지가 있다:

    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

100을 2개 이상 숫자의 합으로 표시하는 데에는 몇가지 방법이 있는가?

--------------------------------------------------------------------------

예시를 제외하면 문제는 2줄 밖에 안되지만, 막상 구현하려 하면 간단한 것이 아니었다. 문제31의 변형이어서 그 때 사용한 방법을 적용하려 보니 31번에서는 8종류의 동전을 이용하는 8중 반복문을 이용해서 구현했는데, 이 문제는 그 경우 99종류의 동전이 있기 때문에 99중 반복문을 구현해야 가능한 것이었다. 그렇게 해결할 수도 있겠지만 문제에서 원하는 방법이 그것이 아니어서 고민을 많이 했는데 해결책이 떠오르지 않아 많이 애를 먹었다.

가장 간단하게 해결하는 것은 동적 프로그래밍을 이용하는 것인데, 다른 사람이 해결한 코드를 보면 간단하지만 왜 그렇게 답이 나오는지 이해가 되지 않아 많이 난감했다.

그래서 관련 내용을 추가로 찾아보니 이 문제는 정수론(number theory)이나 이산수학(Discrete Mathematics)에서 다루는 분할수(Partition Number) 문제라고 한다. 답을 구하는 방법으로 오일러의 오각수 정리, 하디-라마누잔-라데마커 공식과 같은 것이 있는데 오일러의 오각수 정리를 이용해서 답을 구했다. 위키피디아 보다는 나무위키의 분할수 항목에 프로그램으로 구현 가능하도록 공식이 나와 있어 그것을 이용했다.