프로젝트 오일러 148번

We can easily verify that none of the entries in the first seven rows of Pascal's triangle are divisible by $7$:

						1
					1		1
				1		2		1
			1		3		3		1
		1		4		6		4		1
	1		5		10		10		5		1
1		6		15		20		15		6		1

However, if we check the first one hundred rows, we will find that only $2361$ of the $5050$ entries are not divisible by $7$.

Find the number of entries which are not divisible by $7$ in the first one billion $\left ( 10 ^ 9 \right )$ rows of Pascal's triangle.

---

파스칼의 삼각형 처음 $7$ 행까지의 수 중에는 $7$ 로 나누어 떨어지는 수가 없다는 것을 위 그림에서 쉽게 확인할 수 있다.

하지만 처음 $100$ 행까지 $7$로 나누어 떨어지지 않는 수는 전체 $5050$ 개 중 $2361$ 개가 있음을 알 수 있다.

그렇다면 처음 $10^9$ 행까지의 수 중 $7$ 로 나누어 떨어지지 않는 수들은 몇 개나 있을까?

처음에 이 문제를 보면서 파스칼의 삼각형의 제 $n$ 행은 ${_n{\rm C}_r}$ (단, $r=0, \; 1, \; 2, \; \cdots, \; n$) 로 이루어 진다는 사실을 이용하거나 혹은 조합의 성질 ${_{n-1}{\rm C}_{r-1}} + {_{n-1}{\rm C}_r} = {_n{\rm C}_r}$ 을 이용하여 풀 것이란 확신이 있었다. 그러나 그 확신은 점점 실망이 되었고, 좌절이 되었다.

그래서 일단 조합의 성질을 이용하여 무식하게 $7$ 로 나눈 나머지들을 구해보기 시작했다. 여기서는 $7$ 로 나눈 나머지가 $0$ 인지 아닌지만 따지면 되기 때문에 $7$ 로 나눈 나머지가 $0$ 이 아닌 경우는 모두 1로 표시하여 파스칼의 삼각형을 다시 그려 나갔더니, 아주 놀라운 규칙성이 보이기 시작했다.

1) 제 $7$ 행 까지의 규칙

파스칼의 삼각형의 제 $n$ 행에는 $n$ 개의 수들이 나열되고, 문제에서 보는 바와 같이 $7$ 행까지는 $7$ 로 나누어 떨어지는 수가 없으므로 $\dfrac{7 \times 8}{2}=28$ 개의 수가 모두 $1$ 로 나타나게 된다. 

2) 제 $7^2$ 행 까지의 규칙

1)에서 본 7행까지의 삼각형을 $S_1$ 라고 한다면, $7^2$ 행까지는 다음과 같은 규칙성이 나타난다. 

이때, $S_1$ 에서 $7$ 로 나누어 떨어지지 않는 수가 $28$ 개 이므로 $7^2$ 행 까지는 총 $28 \times 28 = 28^2$ 개의 수가 $7$로 나누어 떨어지지 않는다. 

3) 제 $7^3$ 행 까지의 규칙

2) 에서 본 $7^2$ 행 까지의 삼각형을 $S_2$ 라고 한다면, $7^3$ 행 까지는 다음과 같은 규칙성이 나타난다. 

이때, $S_2$ 에서 $7$ 로 나누어 떨어지지 않는 수가 $28^2$ 개 이므로 $7^3$ 행 까지는 총 $28^2 \times 28 = 28^3$ 개의 수가 $7$로 나누어 떨어지지 않는다.

 

$\vdots$

$n+1$) 제 $7^{n+1}$ 행 까지의 규칙

제 $7^{n}$ 행 까지의 삼각형을 $S_{n}$ 라고 한다면, $7^n$ 행 까지는 다음과 같은 규칙성이 있다.

이때, $S_n$ 에서 $7$ 로 나누어 떨어지지 않는 수가 $28^n$ 개 이므로 $7^{n+1}$ 행 까지는 총 $28^n \times 28 = 28^{n+1}$ 개의 수가 $7$ 로 나누어 떨어지지 않는다.

자 이제 대충 규칙성이 보이는가? 이런 규칙성을 알고 있다면 문제를 풀기가 매우 수월해 진다. 정답을 구하기 위해서는 다음과 같은 과정을 거치면 된다.

1) $7^n$ 이 $10^9$ 을 넘지 않는 최대의 자연수 $n$ 은 $10$ 이다. 따라서 $10^9$ 을 $7^10$으로 나누어 보면 몫이 $3$, 나머지가 $152574253$ 이 된다. 따라서 $S_{10}$ 이 세 줄 나열되는 것이므로 $28^{10}$ 이 총 $\dfrac{3 \times 4}{2}=6$ 번 더해지면 된다.

$\therefore {\rm sum} = 6 \times 28^{10}$

2) 이제 1)에서의 나머지 $152574253$ 을 $7^9$ 으로 나누어 보면 몫이 $3$, 나머지가 $31513423$ 이 된다. 여기서 조심해야 할 것이 1)에서 $S_{10}$ 이 세 줄만 등장했으므로 다음 줄은 네 개의 똑같은 삼각형으로 시작하게 된다는 것을 꼭 알아야 한다. 따라서 $S_9$ 네 개가 또 다시 세 줄 등장하게 된다. $S_9$ 가 세 줄이면 총 $\dfrac{3 \times 4}{2} \times 28^9$ 개의 수가 $7$ 로 나누어 떨어지지 않을 것이고, 이것이 네 개 등장하므로 총 $4 \times 6 \times 28^9$ 이 더해져야 한다.

$\therefore {\rm sum}= 6 \times 28^{10} + 4 \times 6 \times 28^9$

3) 또다시 2)에서의 나머지 $31513423$ 을 $7^8$ 으로 나누어 보면 몫이 $5$, 나머지가 $2689427$ 이 된다. 2)에서와 마찬가지로 $S_9$ 가 세 줄만 등장했으므로 다음 줄은 네 개의 똑같은 삼각형으로 시작하게 되고, 여기서는 $S_8$ 이 다섯 줄 등장하므로 총 $4 \times 4 \times \dfrac{5 \times 6}{2} \times 28^8$ 이 $\rm sum$ 에 더해져야 한다. 

$\therefore {\rm sum}= 6 \times 28^{10} + 4 \times 6 \times 28^9 + 4 \times 4 \times 15 \times 28^8$

4) 또다시 3)에서의 나머지 $2689427$ 을 $7^7$ 으로 나누어 보면 몫이 $3$, 나머지가 $218798$ 이 된다. 3)에서 $S_8$ 이 다섯 줄만 등장했으므로 다음 줄은 여섯 개의 똑같은 삼각형으로 시작하게 되고, 여기서는 $S_7$ 이 세 줄 등장하므로 총 $4 \times 4 \times 6 \times \dfrac{3 \times 4}{2} \times 28^7$ 이 $\rm sum$ 에 더해지면 된다.

$\therefore {\rm sum}=  6 \times 28^{10} + 4 \times 6 \times 28^9 + 4 \times 4 \times 15 \times 28^8 + 4 \times 4 \times 6 \times 6 \times 28^7$

$\vdots$

이 과정을 $7^0$ 으로 나눈 몫과 나머지가 나올때까지 반복하면서 ${\rm sum}$ 을 더해나가면 답을 얻을 수 있다.

이해하기 힘들면 그림을 그려가면서 해 보는 것이 도움이 될 것이라 믿어 의심치 않는다.