책 이야기

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를 뺀다든지 하는 몇가지 오류가 있어 수정하는 데 시간은 좀 걸렸지만 재미있게 해결 가능한 문제였다.

모든 제곱근은 연분수로 나타낼 때 주기적이며, 위 형태로 나타낼 수 있다:

예를 들어, √23을 생각해 보자:

이것을 반복하면 위와 같은 확장을 구하게 된다:

이 과정은 위와 같이 요약될 수 있다:

이 순서가 반복되는 것을 볼 수 있다. 간결함을 위해, (1,3,1,8)이 무한히 반복하는 것을 나타내도록 √23=[4; (1,3,1,8)]로 표기한다.

처음 10개의 (무리수인) 제곱근을 연분수로 나타내면:

    √2=[1; (2)], 주기=1

    √3=[1; (1,2)], 주기=2

    √5=[2; (4)], 주기=1

    √6=[2; (2,4)], 주기=2

    √7=[2; (1,1,1,4)], 주기=4

    √6=[2; (1,4)], 주기=2

    √10=[3; (6)], 주기=1

    √11=[3; (3,6)], 주기=2

    √12=[3; (2,6)], 주기=2

    √13=[3; (1,1,1,1,6)], 주기=5

N이 13 이하일 때, 정확히 4개 연분수의 주기가 홀수이다.

N이 1만 이하일 때 주기가 홀수인 연분수는 몇 개인가?

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

뒤에 나오는 여러 문제에서 연분수 개념을 응용해야 빨리 풀 수 있기 때문에 해결의 필요성을 많이 느끼고 있던 것이다. 다시 이 문제를 풀면서도 어렵게 느껴지는 것이, 신기하게도 수기로 연분수의 반복을 계산하면 따라가지는데, 그것을 프로그램에 반영하려 하면 이상하게 논리가 꼬이는 것이다. 몇 시간을 들여다보고 다른 방법으로 접근하는데도 이상하게도 논리가 꼬이면서 진행이 되지 않는다.

논리가 꼬이게 된 이유 중 하나는, 위 √23 예시 a₁의 3번째에서 7과 14를 약분하는 것과 4번째에서 그냥 계산하면 나오는 1+(√23+1)/2를 음수로 바꿀 때 2+(√23-1)/2가 아니고 3+(√23-3)/2이 되는가였는데, 아무리 고민해도 해결되지 않아 인터넷의 힘을 빌리기로 했다.

문제를 해결했던 다른 사람이 이용한 앞 숫자, 분모, 분자를 구하는 공식을 이용해서 해결할 수 있었다. 다만, 연분수 문제가 뒤에도 많이 연관되어 있는데 이해하지 못하고 기계적으로 해결을 해야할 상황이 되어서 조금 슬펐다.