책 이야기

분자가 분모보다 작은 양의 분수를 진분수(proper fraction)라 한다.

어떤 분모 d에 대해 d-1개의 진분수가 있다. 예를 들어, d=12일때 진분수는 다음과 같다.
1/12,2/12,3/12,4/12,5/12,6/12,7/12,8/12,9/12,10/12,11/12.

약분되지 않는 분수를 탄력분수(resilient fraction)이라 부르자.

특정 분모 d에 대해 약분되지 않는 분자의 비율을 R(d)라 정의한다. 예를 들어, R(12)=4/11이다.

실제로, d=12는 R(d)<4/10인 가장 작은 분모이다.

R(d)<15499<94744인 가장 작은 분모 d를 구하시오.

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

약분되지 않는 분수를 학교에서는 기약분수(inreducible fraction)로 배웠는데, 여기에서는 무슨 차이가 있는지 모르겠지만 탄력분수로 정의하고 있다.

처음에는 모든 숫자를 대입해서 계산을 시도했는데, 시간이 너무 많이 걸렸다. 기약분수가 적은 경우를 찾는 형태여서 생각해보니 69번 문제를 변형한 문제처럼 보였다.

일단 많이 나눠주는 수의 곱으로 분모가 되어야 작아질 것이기 때문에 처음에는 짝수를 대상으로 시도했는데, 결과값 패턴을 보니 2와 3의 공배수인 6의 배수가 값이 작은 것이 보였다. 가만히 생각해보니 작은 소수의 곱으로 구성되는 숫자일수록 나눠지는 숫자가 많아 정답에 근접하게 나오게 되는 패턴을 찾았다.

그래서, 일단은 2에서 시작해서 나오는 소수의 곱을 대상으로, 배수를 5번씩 계산해서 정답보다 낮은 경우를 찾도록 했다.(예를 들어, 2의 경우 2,4,6,8,10, 2와3의 곱인 6의 경우 6,12,18,24,30, 2와3과5의 곱인 30의 경우 30,60,90,120,150 등을 계산하도록 했다)

소수의 곱은 생각보다 기하급수로 커졌고, 그 덕분에 정답 또한 생각했던 것 보다는 엄청 큰 값이었고, 답에 근접한 값만 계산하게 했어도 상당한 시간이 필요했다.

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

    1/2=0.5

    1/3=0.(3)

    1/4=0.25

    1/5=0.2

    1/6=0.1(6)

    1/7=0.(142857)

    1/8=0.125

    1/9=0.(1)

    1/10=0.1

Where 0.1(6) means 0.166666⋯, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d<1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

분자가 1인 분수를 단위 분수(unit fraction)이라 한다. 분모가 2에서 10인 단위 분수는 다음과 같이 10진수로 나타낼 수 있다:

    1/2=0.5

    1/3=0.(3)

    1/4=0.25

    1/5=0.2

    1/6=0.1(6)

    1/7=0.(142857)

    1/8=0.125

    1/9=0.(1)

    1/10=0.1

0.1(6)은 0.166666⋯을 의미하고, 1자리의 반복 사이클을 가지고 있다. 1/7은 6자리의 순환마디가 있음을 알 수 있다. d<1000일 때, 1/d이 가장 긴 순환마디를 가지는 d를 찾으시오.

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

분수 값에서 순환소수 값을 구하는 방법을 알면 쉽게 풀 수 있고, 이것은 초등학교 산수 수준의 문제인 것 같기는 한데 어떻게 구하는 지 전혀 아이디어가 떠오르지 않아 보류하고 지나갔던 문제이다.

다시 봐도 아이디어가 떠오르지 않아 분수를 순환소수로 구하는 요령을 인터넷으로 검색하고 그것을 파이썬 코드로 만들어서 답을 구할 수 있었다. 9를 계속 만들어가면서 나눠지면 그 때 있는 9의 갯수가 순환마디의 크기를 뜻하는 것이 되는데, 예를 들어, 분모가 6일 때 90을 나눌 수 있고, 이 때 9는 1개 있으므로 순환마디는 1이고, 분모가 7일 때 999999을 나눌 수 있고, 이 때 9가 6개 있으므로 순환마디 6이 된다.

2~999까지의 반복문 안에, 9의 갯수(순환마디)를 찾는 2개의 반복문으로 구성해서 문제를 풀었고, 답을 구하는데 28초가 걸려 그리 성능이 좋은 방법으로 구현하지 않았다는 것을 알았지만 묵혀둔 미결 문제를 해결한 기쁨이 더 컸다.

루트2는 무한하게 반복되는 분수로 표현될 수 있다.

처음 4번의 반복을 확장하면 위 그림과 같다:

다음 3번 확장은 99/70, 239/169, 577/408이지만, 8번째 확장은 1393/985이며 분자의 자릿수가 분모 자릿수보다 크게 되는 첫 숫자이다.

처음 1천번 확장에서 몇 개의 분수에서 분자가 분모보다 자릿수가 더 큰가?

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

이 문제에서 루트2를 구하는 과정을 잘 이해했으면, 뒤에 연계되어 나오는 연분수 문제들을 쉽게 해결할 수 있었는데 너무 기계적으로 간단하게 해결해버렸다.

가만히 살펴보면 분모는 직전 분모x2와 2번 직전 분모를 합한 값이며, 그 때 분자는 1을 빼면 직전 분모 값이 되는 것이 보였다. 예를 들어, 3/2, 7/5 다음 수의 분모는 5x2+2=12이며, 분자는 1을 제외하면 5가 되므로 1+5/12=17/12가 된다.

이 과정을 반복하면서 자릿수가 차이나는 경우를 찾는 것으로 간단하게 해결되었다.

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000

무리수인 10진 분수는 양의 정수를 연결하여 만들어진다:

0.123456789101112131415161718192021...

분수 부분의 12번째 자리 숫자는 1이다.

만약 d_n 이 분수의 n번째 자릿수를 나타낸다면, 다음 표현식의 값을 구하시오.

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000

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

위 특성을 가지는 숫자를 문제 제목인 챔퍼나운 수(Champernowne's constant)라고 부른다고 한다.

1부터 계속 커지는 숫자를 붙여나가는 문자열을 만들면서 1, 10, 100, 1000, 10000, 100000, 1000000번째 숫자를 구하고 그 값을 모두 곱하면 되는 문제이다. 구현하는 방법은 다양하겠지만 프로젝트 오일러 문제를 차례대로 풀어왔다면 그렇게 어렵지 않게 해결 가능한 문제이다.

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

분수 49/98은 경험이 적은 수학자가 잘못된 방법을 믿고 9를 지우는 방법으로 단순화시켜도 49/98=4/8은 맞게 되는 신기한 분수이다.

30/50=3/5와 같은 분수는 흔한 예시로 생각하자.

이런 유형의 분수에서 분자와 분수가 2자리 숫자이고 1 미만의 값이 되는 흔하지 않은 예시는 정확하게 4가지가 있다.

이 4가지 분수를 곱해서 약분했을 때, 분모의 값을 구하시오.

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

2자리 숫자 분자, 분모에서 공통된 숫자를 하나 지웠을 때 지우기 전의 숫자와 값이 동일한 것을 4개 찾는데, 제약사항으로 지우는 숫자는 0이 아니고, 남은 두 수가 같거나 분자에 있는 수가 커서도 안된다.

분자는 11~98, 분모는 분자+1~99까지 반복하면서 나온 분수에서 동일한 수가 있으면, 그 수를 삭제하고, 남은 수와 애초의 분수가 동일한 분수 4개를 찾고, 분수 4개를 곱한 후, 약분해서 구하면 된다. 이 경우 지우는 숫자가 0이 안되도록 처리해 주는 부분이 추가로 필요하다.

조금 더 빨리 계산하려면, 공통되는 수 1자리, 분자 나머지 1자리, 분모 나머지 1자리를 대상으로 3번 중첩되는 반복문 형태로 구현하는 것도 가능할 것 같다. 속도는 나쁘지만 위 방법으로도 답을 어렵지 않게 구해서 성능개선은 하지 않았다.