프로젝트 오일러 132번

A number consisting entirely of ones is called a repunit. We shall define $R(k)$ to be a repunit of length $k$.

For example $R(10)=1111111111=11\times 41 \times 271 \times 9091$, and the sum of these prime factors is $9414$.

Find the sum of the first fort prime factors of $R \left ( 10^9 \right )$.

---

숫자 $1$ 로만 이루어진 수를 repunit 이라고 한다. $R(k)$ 를 $k$ 개의 $1$ 로 이루어진 수라고 하자. 예를 들어, $R(10)=1111111111$ 이다. 이 때, $R(10)$ 은 $11 \times 41 \times 271 \times 9091$ 로 소인수 분해 된다. 그리고 이들 소인수들의 총합은 $9414$ 가 된다.

$R \left (10^9 \right )$ 의 소인수를 오름 차순으로 나열했을 때, 처음 $40$ 개 소인수들의 합을 구하시오.  

고등학교 수학 시간에도 가끔 등장하는 수열이 $1, \; 11, \; 111, \; 111, \; \cdots$ 이다. 아마 한국에서 고등학교를 제대로(?) 졸업했다면 이 수열의 일반항이 $\dfrac{10^n -1}{9}$ 라는 것 쯤은 알고 있을 것이라 믿어 의심치 않는다. 그렇다면 $\dfrac{10^n -1}{9}$ 이 $p$ 로 나누어 떨어지는 소수 $p$ 들을 찾으면 된다. 소수 $p$ 로 나누었을 때의 몫을 $Q$ 라고 하면 $\dfrac{10^n -1}{9} = Qp$ 가 성립할 것이고, 결국 $10^n = Q\times (9p) +1$ 이 된다. 즉, $10^n$ 을 $9p$ 로 나누었을 때의 나머지가 $1$ 이 되는 소수 $p$ 들을 찾으면 된다.

그런데 이 문제에서는 $n= 10^9$ 인 경우를 다뤄야 한다. 설명은 쉬웠지만 $10^{10^9}$ 을 $9p$ 로 나눈다는 것 자체가 상당히 어려운 일이다. 제 아무리 컴퓨터라 할지라도... 그래서 우리는 거듭제곱을 어떤 수로 나눈 나머지를 더욱 빠르게 구할 수 있는 방법에 대해서 생각해 봐야 한다.

이를 위하여 우리는 다음의 두 가지를 알고 있어야 한다.

1. $ab$ 를 $m$ 으로 나눈 나머지는 $a$ 를 $m$ 으로 나눈 나머지와 $b$ 를 $m$ 으로 나눈 나머지의 곱이다.

2. 거듭제곱을 빠르게 하기 위한 방법

$b^ e$ 을 빠르게 구하기 위해서는 $e = \sum \limits_{i=0}^{n-1} a_i 2^i$ 의 형태로 표현한다. 즉, $$b^e = b^{\sum \limits_{i=0}^{n-1} a_i 2^i} = \prod \limits_{i=0}^{n-1} \left ( b^{2^i} \right ) ^ {a_i}$$

로 표현하는 것이다. 또한 이 과정에서 $b^e$ 을 $m$ 으로 나눈 나머지를 구할 때는, 위의 1번 성질을 이용하여 곱하는 놈과 곱해지는 놈을 $m$ 으로 나눈 나머지들을 곱하여 그 결과를 다시 $m$ 으로 나눈 나머지를 구하는 방식으로 쉽게 나머지를 구할 수 있다. 

다음의 파이썬 코드는 위의 두 가지 성질을 이용하여 $b^e$ 을 $m$ 으로 나눈 나머지를 구하는 함수이다.

def exp_mod(b, e, m):
	r = 1
	result = list(bin(e))[2:]
	result.reverse()
	for i in range(len(result)):
		if result[i] == '1':
			r = r * b % m
		b = b * b % m
	return r

여기서 $r$ 이 나머지를 나타내는데, 고등학교 수학 시간에 순서도 공부하듯이, $r$ 과 $b$ 의 테이블을 만들어 변화 과정을 살펴보면 충분히 이해가 갈 것이다.

파이썬에서는 위의 예제 코드에서 보여지는 exp_mod 와 똑같은 역할을 하는 pow 함수를 기본으로 제공하고 있다. 속도는 pow 쪽이 더 빠르다. 둘을 비교해 보는 것도 재미가 쏠쏠할 듯...