일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- NumPy
- Big-Oh notation
- 랜덤 순서 배열
- matrix fo a linear transformation
- matrix-vector product
- 코틀린 시작하기
- solutions of matrix equation
- 배열 섞기
- python
- matrix trnasformations
- nontrivial solution
- Big Theta
- 재귀함수
- 빅세타
- 알고리즘 분석의 실례
- 빅오 표기법
- Big-Oh 예제
- 코틀린 Hello World!
- homogeneous linear system
- Big Omega
- recursive algorithms
- 일차변환
- itertools
- 이진 탐색
- trivial solution
- linear dependence
- 빅오메가
- nonhomogeneous linear system
- one-to-one
- Big-O 예제
- Today
- Total
코딩 연습
프로젝트 오일러 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\) 행 내외의 코딩으로 해결 할 수 있다.
'project euler with python' 카테고리의 다른 글
프로젝트 오일러 76번 (0) | 2016.03.15 |
---|---|
프로젝트 오일러 31번 (0) | 2016.03.15 |
프로젝트 오일러 69번 (0) | 2016.03.15 |
프로젝트 오일러 68번 (0) | 2016.03.15 |
프로젝트 오일러 67번 (0) | 2016.03.15 |