프로젝트 오일러 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}\) 을 더해나가면 답을 얻을 수 있다.

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