프로젝트 오일러 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 쪽이 더 빠르다. 둘을 비교해 보는 것도 재미가 쏠쏠할 듯...