일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 코틀린 Hello World!
- trivial solution
- recursive algorithms
- 알고리즘 분석의 실례
- nonhomogeneous linear system
- 재귀함수
- 코틀린 시작하기
- matrix fo a linear transformation
- 랜덤 순서 배열
- python
- linear dependence
- matrix trnasformations
- itertools
- 이진 탐색
- Big-Oh notation
- 일차변환
- Big-Oh 예제
- 빅오 표기법
- 빅세타
- solutions of matrix equation
- Big Theta
- matrix-vector product
- 빅오메가
- homogeneous linear system
- nontrivial solution
- Big-O 예제
- Big Omega
- one-to-one
- NumPy
- 배열 섞기
- Today
- Total
코딩 연습
프로젝트 오일러 66번 본문
66번 문제는 다음과 같다.
Consider quadratic Diophantine equations of the form:
x2 – Dy2 = 1
For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 1.
It can be assumed that there are no solutions in positive integers when D is square.
By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:
32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1
Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.
Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.
결국 D가 주어졌을 때, \(x^2 -Dy^2 =1\) 을 만족시키는 가장 작은 자연수 \(x\) 를 찾는 것이 해야할 일이다.
만약 D가 1부터 1000까지 변할 때 (물론 D는 완전제곱수가 아니어야 한다.) 위의 조건을 만족하는 \(x\) 들을 모두 찾는다면 가장 큰 \(x\) 값이 나오는 \(D\) 는 얼마일까? 뭐 이런걸 묻는 문제이다.
사실 이 문제는 상당히 단순하게 생각할 수 있다. \(x, \;y\) 를 1부터 증가시키면서 조건을 만족하는 자연수 \(x, \; y\) 값을 찾으면 되기 때문이다. 만약 이런 생각으로 문제를 풀다가 해결책이 없어서 여기까지 흘러 들어왔다면 분명히 \(D=61\) 일 때, \(x, \;y\) 를 찾지 못했을 가능성이 농후하다. 똑같은 과정을 필자도 겪었기 때문이다.
위에 주어진 식 \(x^2-Dy^2=1\) 은 pell's equation 이란 것이다. 이 펠 방정식의 풀이법을 정확히 아는 것은 상당한 수학적 지식을 요구할 뿐만 아니라 프로그래밍 공부를 하는 목적에 어울리지 않기 때문에 (이렇게 생각해야만 프로그래밍 공부를 계속할 수 있지 않을까? 수학적인 부분때문에 프로그래밍을 포기할 수 없으므로) 여기서는 간단하게 펠 방정식 풀이의 접근 방법을 소개하고자 한다.
주어진 방정식을 다음과 같이 변형해 보자.
\[ \sqrt{D}=\dfrac{\sqrt{x^2-1}}{y} \approx \dfrac{x}{y}\]
위 식을 만족하는 자연수 \(x, \;y\) 는 결국 \(\sqrt{D}\) 의 근삿값을 나타내는 유리수의 분자와 분모가 된다고 생각할 수 있다. 이 근삿값은 이미 64번에서 봤던 방법으로 연분수 전개(continued fraction expansion) 로 부터 구할 수 있다.
예를 들어,
\[\begin{split} \sqrt{7} &= 2+\sqrt{7}-2 =2+\dfrac{1}{\dfrac{1}{\sqrt{7}-2}}=2+\dfrac{1}{\dfrac{\sqrt{7}+2}{3}} \\ &= 2+\dfrac{1}{1+\dfrac{\sqrt{7}-1}{3}}=2+\dfrac{1}{1+\dfrac{1}{\dfrac{\sqrt{7}+1}{2}}} \\ &=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{\sqrt{7}-1}{2}}} =2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{\dfrac{\sqrt{7}+1}{3}}}} \\ &= 2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{\sqrt{7}-2}{3}}}} = \cdots \end{split}\]
이 되므로, 이를 단계단계 계산하여 \(\sqrt{7}\) 의 근삿값을 찾아내면
\(\sqrt{7}=2\)
\(\sqrt{7}=2+\dfrac{1}{1}=3\)
\(\sqrt{7}=2+\dfrac{1}{1+\dfrac{1}{1}}=\dfrac{5}{2}\)
\(\sqrt{7}=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1}}}=\dfrac{8}{3}\)
\(\vdots\)
이렇게 구한 근삿값들을 나열해 보면
\[ \dfrac{2}{1}, \; \dfrac{3}{1}, \; \dfrac{5}{2}, \; \dfrac{8}{3}, \; \dfrac{37}{14}, \cdots\]
가 된다. 이 근삿값들을 이용하여 펠 방정식의 해를 찾으면
\[2^2 - 7\cdot 1^2=-3\]
\[3^2-7 \cdot 1^2 =2\]
\[5^2 - 7 \cdot 2^2 = -3\]
\[8^2 - 7 \cdot 3^2 =1\]
따라서 \(x=8, \; y=3\) 이 되는 것을 알 수 있다.
프로그래밍을 할 때, 일단 \(\sqrt{D}\) 의 근삿값을 연분수 전개로 찾아낸 다음, 분자와 분모를 각각 \(x, \; y\) 에 대입하다가 등식을 만족하는 \(x, \; y\) 를 찾아내면 된다. 이 방법으로 하게 되면 매우 빠른 시간 안에 문제를 해결 할 수 있다.
참고로 \(D=661\) 일 때, \(x=16421658242965910275055840472270471049\) 의 최댓값을 갖게 된다. 따라서 66번의 정답은 \(661\) 이다.
'project euler with python' 카테고리의 다른 글
프로젝트 오일러 68번 (0) | 2016.03.15 |
---|---|
프로젝트 오일러 67번 (0) | 2016.03.15 |
프로젝트 오일러 59번 (0) | 2016.03.15 |
프로젝트 오일러 54번 (0) | 2016.03.15 |
프로젝트 오일러 51번 (0) | 2016.03.15 |