책 이야기

분자가 분모보다 작은 양의 분수를 진분수(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 등을 계산하도록 했다)

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

"_"가 숫자 한 자리이며, 제곱값이 1_2_3_4_5_6_7_8_9_0인 양의 정수를 구하시오.

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

난이도 5%인 문제여서 그런지 그나마 단순한 방법으로 해결가능했다.

일단 19자리 숫자이면서 1의 자리에 0, 백 자리에 9, 만 자리에 8, 백만 자리에 7, 억 자리에 6, 백억 자리에5, 조 자리에 4, 백조 자리에 3, 경 자리에 2, 백경 자리에 1이 들어가는 숫자를 구하면 되는데,  첫 자리가 1로 시작하므로 제곱하여 백경이 되는 1,000,000,000부터 시작할 것이고, 첫 자리가 2보다 작아야 하므로 √2*1,000,000,000 보다는 작아야 할 것이다.

그리고, 1의 자리가 0이므로 마지막 숫자는 0이 되므로 이 사이의 숫자를 반복문을 통해 계산해서 어렵지 않게 구할 수 있었다.

양의 정수 x, y, z가 등차수열의 연속된 요소일 때, x2-y2-z2=n으로 구해지는 가장 작은 양의 정수 n은 n=27일 때 정확하게 2개의 해답이 있다:

342-272-202=122-92-62=27.

정확하게 10개의 해답이 있는 최소값은 n=1155일 때이다.

10개의 해답이 있는 1백만 이하의 n은 몇 개 인가?

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

등차수열이기 때문에 처음에는 x를 기준으로, x2-(x-a)2-(x-2a)2=n으로 수식을 만들어서, 정리하니 x2-6ax+5a2=-n이어서, (x-a)(x-6a)=-n이 되었다. 모양은 좀 이상했지만 처음 값 x와, 차이 a 기준으로 n의 약수의 곱이 된다는 것을 알 수 있었다.

(제대로 접근한 사람은 가운데 y를 기준으로 (y+a)2-y2-(y-a)2=n으로 수식을 만들어서, 전개하면 4ay-y2=n이 되고, 차이 a 기준으로 정리하면 a=(n+y2)/4y가 된다)

처음에는 약수의 갯수만 관련이 있다고 생각하고 약수가 20개 인 수(두 수의 곱이므로 절반인 10개의 해답을 만드는 수로 추정)의 갯수를 찾도록 구현했는데, 약수 만드는 함수의 성능이 나빠서 시간이 너무 많이 걸리고, 이를 개선해서 조금 빨리 돌아가도록 했는데 오답이 나왔다.

다시 확인해보니, 후보가 되는 것은 약수가 맞지만 두 약수의 곱이 아니기 때문에 약수를 대상으로 등차수열 조건(a=(n+y2)/4y, a<y, a는 정수)을 만족하는지 확인해야 되는 것이었다. 그렇게, 단순히 약수의 갯수를 세는 것이 아니라 약수를 대상으로 등차수열을 만들 수 있는 것이 몇 개인지 확인하도록 변경해서 답을 구할 수 있었다.

그리고, 처음에는 n의 약수를 1~n/2까지 비교하도록 되어 있던 함수 성능을 개선한 이후에야 수분 내에 답을 구할 수 있어서, 성능의 중요성을 다시 한 번 느꼈다.

1로만 구성된 숫자를 repunit이라 부른다. R(k)를 길이가 k인 repunit이라 정의하자. 예를 들어, R(6)=111111이다.

gcd(n,10)=1인 양의 정수 n에 대해 언제나 R(k)를 n으로 나눌 수 있는 k가 존재한다. 그러한 k 중 최소값을 A(k)라 하자. 예를 들어, A(7)=6이고, A(41)=5이다.

5보다 큰 모든 소수에 대해, p-1은 A(p)로 나눠진다. 예를 들어, p=41일 때, A(41)=5이며 40은 5로 나눠진다.

그러나, 합성수 중 이러한 특성을 가지는 것이 드물지만 있다. 처음 5개 숫자는 91, 259, 451, 481, 703이다.

gcd(n,10)=1이고 n-1을 A(n)으로 나눌 수 있는 처음 25개 숫자의 합계를 구하시오.

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

129번 문제를 해결했으면, 코드를 조금만 수정하면 해결 가능한 문제이다.

기존에는 검증 대상이 되는 숫자에서  2의 배수, 5의 배수를 제외했지만, 소수 목록을 만들어서 소수를 검증 대상에서 제외하는 과정을 추가하고, n-1을 A(n)으로 나눠지는 숫자를 찾으면 된다.

문제에서 요구한대로 코딩했는데도 처음에 오답이 나와 원인을 분석하는 데 시간이 조금 걸렸다. 원인을 찾아보니, 검증대상에서 제외할 소수목록을 1만 이하의 숫자를 대상으로 만들었는데 실제로는 1만 이상의 숫자까지 대상이 되면서, 제외되어야 하는 소수가 목록에 포함되었던 것이 문제였다.

1로만 구성된 숫자를 repunit이라 부른다. R(k)를 길이가 k인 repunit으로 정의하자. 예를 들어, R(6)=111111이다.

gcd(n,10)=1인 양의 정수 n에 대해 언제나 R(k)를 n으로 나눌 수 있는 k가 존재한다. 그러한 k 중 최소값을 A(n)이라 하자. 예를 들어, A(7)=6이고, A(41)=5이다.

A(n)이 10을 초과하는 최초의 n은 17이다.

A(n)이 1백만을 초과하는 최초의 n을 구하시오.

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

문제를 조금 부연설명하면 gcd(n,10)=1이라 했으므로, n은 2, 5와 공약수가 없는 숫자이다(2와 5로 나눠지지 않는다). 이것만 가지고 구현했을 때 예시에서 나온 A(7), A(41)이나 결과가 10이 넘는 A(n)의 값은 쉽게 구할 수 있는데, 결과가 1백만을 초과하는 것을 구하려면 시간이 대책없이 필요했다.

처음 2부터 입력해서 나온 n, k의 결과값 목록을 보면서도 생각하지 못했는데, 오일러 프로젝트를 풀고 있는 다른 블로거의 설명을 보고 빨리 해결하는 방법을 구할 수 있었다.

중요한 단서는 k가 n보다 클 수 없다는 것이다. 그것을 보고 시작지점을 변경해서 빠른 시간 내에 답을 구할 수 있었다.