책 이야기

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보다 클 수 없다는 것이다. 그것을 보고 시작지점을 변경해서 빠른 시간 내에 답을 구할 수 있었다.