프로젝트 오일러 72번

72번 문제는 다음과 같다.

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

결국 이 문제는 \(2\) 보다 큰 자연수 \(d\)에 대하여 \(\dfrac{n}{d}\) ( \(n, \; d\) 는 서로소인 자연수, \(n < d\)) 의 개수를 구하는 문제이다. 즉, \(d\) 보다 작은 자연수 중 \(d\) 와 서로소인 자연수의 개수가 몇 개인지를 \(2 \le d \le 1000000\) 범위에서 구해야 한다. 물론 구하는 것은 그리 어렵지 않은 일이겠지만 문제는 시간이다. 아마 일반적인 방법으로 \(d\) 와 \(n\) 의 소인수를 모두 구하여 서로소인지 아닌지를 확인하는 방법을 사용할 수 있지만, 이 경우 엄청나게 많은 시간이 소요된다. 이 문제는 에라토스 체의 방법을 살짝 빌려오면 쉽게 해결할 수 있다.

예를 들어 \(d=6\) 인 경우를 생각해 보자. 이 경우 \(\dfrac{1}{6}, \; \dfrac{5}{6} \) 의 두 개를 찾을 수 있다. 이 두개를 어떤 식으로 찾아낼 수 있는지 생각해 보자. Euler's phi (totient) function에 의하면 \(6\) 의 소인수는 \(2\) 와 \(3\) 이므로  \(\phi (6)=6 \times \left ( 1-\dfrac{1}{2} \right ) \left ( 1 - \dfrac{1}{3} \right ) \) 가 된다. 이 식을 잘 살펴보면 \[\begin{split} 2 \cdot 3 \cdot \left ( 1-\dfrac{1}{2} \right ) \left ( 1 - \dfrac{1}{3} \right ) &=(2-1)(3-1) \\ &= 2\cdot 3 -2 -3 +1 \\ &=  (2 \cdot 3 -3) -(2-1) \end{split} \] 와 같다. 마지막에 있는 \( (2 \cdot 3 -3) -(2-1) \) 가 어떤 의미를 갖는지를 알기 위해 다음과 같은 생각을 해 볼 수 있다.

먼저 \(6\) 이하의 수 중 \(6\) 과 서로소인 수의 개수를 찾으려면 \(1\) 부터 \(6\) 까지 \(6\) 개의 수 중 \(2\) 의 배수와 \(3\) 의 배수를 제거하고 남은 수가 몇 개인지 알아 보면 된다. . \(1\) 부터 \(6\) 까지 \(2\) 의 배수는 \(6 \div 2\) 개 만큼 있으므로 일단 \(3\) 개를 제거한다. 이 부분이 \((2\cdot 3 - 3)\) 에 해당한다고 보면 된다. 이제 남아 있는 \(3\) 개의 수 중에서 \(3\) 의 배수만 제거하면 되는데, 남아 있는 숫자의 개수인 \(3\)을 \(3\) 으로 나눈 몫이 바로 남아 있는 수 중 \(3\) 의 배수의 개수가 된다. 따라서 \( 3 \div 3\) 을 더 빼주면 된다. \((2 \cdot 3 -3)\) 을 \(3\) 으로 나눈 몫이 \((2-1)\) 이므로 \((2-1)\) 을 한 번 더 빼준다고 생각하면 된다. 그래서 얻어지는 식이 \( (2 \cdot 3 -3) -(2-1) \) 인 것이다.

\(75= 3 \times 5^2\) 에 대해서도 한 번 생각해 보자. \[\begin{split} \phi (7)&= 3 \cdot 5^2 \cdot \left ( 1 - \dfrac{1}{3} \right ) \left( 1 - \dfrac{1}{5} \right ) \\ &= \left ( 3 \cdot 5^2 - 5^2 \right ) \left ( 1- \dfrac{1}{5} \right ) \\ &=  3 \cdot 5^2 - 5^2 - 3 \cdot 5 + 5 \\ &= \left ( 3 \cdot 5^2 - 5^2 \right ) - ( 3 \cdot 5 - 5 ) \end{split} \] 여기서도 \( 3 \cdot 5^2\) 을 \(3\) 으로 나눈 몫 \(5^2\) 을 빼주고, 그 결과인 \( 3 \cdot 5^2 -5^2\) 을 다시 \(5\) 로 나눈 몫 \( 3 \cdot 5 -5\) 를 더 빼준 형태라는 것을 볼 수 있다. 소인수가 \(3\) 개 이상인 경우에도 이 룰이 성립한다. 이 룰을 문제에서 예로 주어진 \( d \le 8\) 인 경우에 적용시켜 보자.

먼저 \(1\) 부터 \(8\) 까지의 숫자들을 나열해 보자.

\[1, \;2, \; 3, \; 4, \; 5, \; 6, \; 7,\; 8\]

이 중 짝수 번째에 있는 숫자들은 모두 \(2\)를 소인수로 가지므로  자신 보다 작거나 같은 \(2\) 의 배수들을 모두 제거해야 하므로 \(2\) 로 나눈 몫들을 모두 빼 준다.

\[ 1, \;2-1, \;3, \; 4-2, \; 5, \; 6-3, \; 7, \; 8-4 \;\;\; \rightarrow\;\;\; 1, \; 1, \; 3,\; 2,\; 5, \; 3, \; 7, \; 4\]

또한 원래 숫자들의 나열에서 \(3\)의 배수 번째에 있는 숫자들은 모두 \(3\) 을 소인수로 가지므로 위의 결과로 얻은 숫자들의 나열에서 \(3\)의 배수번째 있는 숫자들은 자기 자신을 \(3\) 으로 나눈 몫을  빼 줘야 한다.

\[ 1, \; 1, \; 3-1, \; 2, \;5, \; 3-1, \; 7, \; 4 \;\;\; \rightarrow \;\;\; 1, \; 1,\;2,\;2,\;5,\;2,\;7,\; 4\]

계속해서 원래 숫자들의 나열에서 \(5\)의 배수 번째에 있는 숫자들은 모두 \(5\)를 소인수로 가지므로 위의 결과로 얻은 숫자들의 나열에서 \(5\)의 배수 번째에 있는 숫자들은 자기 자신을 \(5\) 로 나눈 몫을 빼 줘야 한다. 

\[1, \; 1,\;2,\;2,\;5-1,\;2,\;7,\; 4\;\;\; \rightarrow \;\;\; 1, \; 1,\;2,\;2,\;4,\;2,\;7,\; 4\]

마지막으로 원래 숫자들의 나열에서 \(7\)의 배수 번째에 있는 숫자들은 모두 \(7\)를 소인수로 가지므로 위의 결과로 얻은 숫자들의 나열에서 \(7\)의 배수 번째에 있는 숫자들은 자기 자신을 \(7\) 로 나눈 몫을 빼 줘야 한다. 

\[1, \; 1,\;2,\;2,\;4,\;2,\;7-1,\; 4\;\;\; \rightarrow \;\;\; 1, \; 1,\;2,\;2,\;4,\;2,\;6,\; 4\]

최종적으로 얻은 숫자들의 나열이 어떤 의미인지 알아보자.

\[1, \; 1,\;2,\;2,\;4,\;2,\;6,\; 4\]

마지막에 있는 \(4\) 는 \(8\) 보다 작은 자연수 중 \(8\) 과 서로소인 자연수들의 갯수이다.

마지막에서 두 번째 있는 \(6\) 은 \(7\) 보다 작은 자연수 중 \(7\) 과 서로소인 자연수들의 갯수이다.

나머지 숫자들도 동일한 의미를 지닌다. 다만 맨 앞에 등장하는 \(1\) 은 자릿수를 맞추기 위해서 필요한 수였을 뿐, 이 문제에서 별 의미는 없다고 봐야 한다. 따라서 맨 앞에 등장하는 \(1\) 을 제외한 나머지 \(7\) 개 수 들을 모두 더하면 우리가 구하는 \(21\)을 얻게 되는 것이다.

72번을 풀기 위한 프로그래밍을 할 때, 위에서 본 과정을 1000000까지 적용시키면 된다.

python의 경우 \(10\) 행 내외의 코딩으로 해결 할 수 있다.