글
*전 세계에서 248번째로 풀었다. -_-;
다 풀고나서 내 정답을 확인하기를 바란다. 정답은 일단 가장 끝에다가 가려둔다.
오래간만에 수학 문제를 발견했다.
문제의 원문은 http://projecteuler.net/index.php?section=problems&id=207 에서 찾을 수 있다.
이 문제를 풀기 위해서 고율님의 아이디어 대로 $X=2^t$ 로 치환한다.
그럼 주어진 식은 $X^2-X-k=0$이라는 2차 방정식이 된다. 이 2차 방정식을 풀어보자.
$X=\frac{1}{2} \pm \frac{1}{2}\sqrt{1+4k}$
이 된다.
다시 X를 원래대로 치환하면
$2^t=\frac{1}{2} \pm \frac{1}{2}\sqrt{1+4k}$
이 된다. 그런데 $2^t$는 양수밖에 없으므로
$2^t=\frac{1}{2} + \frac{1}{2}\sqrt{1+4k}$
이 될 것이다. $2^t$가 정수가 되어야 한다는 조건이 있으므로, 우변도 정수가 되어야 한다. 근데 정수가 아닌 유리수인 1/2가 있기 때문에 좀 곤란해 보인다. 이 부분을 증명하고 넘어가자. 일단 1+4k가 어떤 정수의 제곱수가 아니라고 하자. 그렇다면 우변은 무리수가 되므로, 반드시 1+4k는 어떤 정수의 제곱수가 되어야만 한다. 또한, 1+4k가 어떤 정수의 제곱수라면, 1+4k는 홀수이므로 그 제곱근 역시 홀수이다. 홀수의 절반에 1/2을 더하면 정수가 나온다. 따라서 1+4k가 제곱수이기만 하면 된다. 즉, t가 파티션이 될 조건은 1+4k가 제곱수가 될 조건과 같다. 그럼 m보다 작은 k에 대해서 1+4k가 제곱수인지 조사하면 된다. 1+4k의 제곱근을 2n+1이라고 가정하자. 그럼 $1+4k=4n^2+4n+1$ 이므로 $k=n(n+1)$ 이 된다. 이 말은, $k=n(n+1)$조건을 만족하기만 하면 t는 파티션이 된다는 뜻이다. 그럼 m보다 작은 n(n+1)인 숫자들을 찾아내면 된다.
이제, t가 양의 정수(앞으로는 그냥 정수라고 하겠다)인 경우를 생각해 보자.
$2^t=\frac{1}{2} + \frac{1}{2}\sqrt{1+4k}$
여기에 k=n(n+1)을 대입해 보자.
$2^t = 1+ 2n+1 = 2(n+1)$
이렇게 식이 변했다. 앞에 있는 2를 떼어 내고도 t가 정수가 되기 위해서는 n+1 또한 2의 거듭제곱수이면 충분하다.
따라서 t가 perfect partition이 되기 위해서는 어떤 양의 정수 q에 대해서 $n=2^q-1$ 형태면 충분하다.
자, 이제 m에 대해 t가 정수가 되는 k가 몇개나 되는지 따져볼 차례다.
k=n(n+1)이었고, $n=2^q-1$ 형태였으므로, 이걸 다시 k에 대입하면
$k=4^q-2^q$
가 된다.
이제, q에 1부터 하나씩 대입해 가면서 문제에서 주어진 m이 k보다 작은 경우가 몇개나 되는지 보면 된다.
따라서, 다음의 부등식을 만족하는 최대의 q값을 구하면 된다.
$4^q -2^q \leq m$
정리하자면 다음과 같다.
1.n(n+1)이 m보다 작게 되는 양의 정수 n이 몇개인지 조사한다. 이 숫자를 A(m)라고 정의한다.
2.그러한 양의 정수 n중에서 n+1이 2의 거듭제곱수가 되는 경우가 몇개인지 조사한다. 이 숫자를 B(m)라고 한다.
3. P(m)=A(m)/B(m) 이다.
그런데, 반대로 생각해 보자. 어차피 k는 n(n+1)이 되기만 하면 되므로, $n=2^q-1$을 계산해서 q를 1씩 더하고, 그때마다 n이 어떻게 커지는지를 살펴보면 되지 않을까?
어쨌거나 이 문제를 풀게 된 알고리즘은 다음과 같다.
1. n을 계속해서 1씩 키워나간다.
2. n+1이 2의 거듭제곱수가 되면 q를 1만큼 증가시킨다.
3. q/n<1/12345가 되면 멈추고 n*(n+1)을 출력한다.
출력된 값이 m의 최소값이다.
덧붙임.
문제 해결하는 코드를 C로 짰는데 32비트 머신에서 쓸 수 있는 숫자의 자릿수가 너무 작아서 (답이 4294967296을 넘는 것 같음) 풀지 못하였다.
이건 뭐 페르마의 대정리도 아니고...-_-;;;;
결론적으로.
답이 32비트 머신에서 쓸 수 있는 숫자(4294967296)보다 많은 것은 사실이었다. 그래서 마지막 계산은 공학용 계산기를 썼다.
정답
다 풀고나서 내 정답을 확인하기를 바란다. 정답은 일단 가장 끝에다가 가려둔다.
오래간만에 수학 문제를 발견했다.
문제의 원문은 http://projecteuler.net/index.php?section=problems&id=207 에서 찾을 수 있다.
이 문제를 풀기 위해서 고율님의 아이디어 대로 $X=2^t$ 로 치환한다.
그럼 주어진 식은 $X^2-X-k=0$이라는 2차 방정식이 된다. 이 2차 방정식을 풀어보자.
$X=\frac{1}{2} \pm \frac{1}{2}\sqrt{1+4k}$
이 된다.
다시 X를 원래대로 치환하면
$2^t=\frac{1}{2} \pm \frac{1}{2}\sqrt{1+4k}$
이 된다. 그런데 $2^t$는 양수밖에 없으므로
$2^t=\frac{1}{2} + \frac{1}{2}\sqrt{1+4k}$
이 될 것이다. $2^t$가 정수가 되어야 한다는 조건이 있으므로, 우변도 정수가 되어야 한다. 근데 정수가 아닌 유리수인 1/2가 있기 때문에 좀 곤란해 보인다. 이 부분을 증명하고 넘어가자. 일단 1+4k가 어떤 정수의 제곱수가 아니라고 하자. 그렇다면 우변은 무리수가 되므로, 반드시 1+4k는 어떤 정수의 제곱수가 되어야만 한다. 또한, 1+4k가 어떤 정수의 제곱수라면, 1+4k는 홀수이므로 그 제곱근 역시 홀수이다. 홀수의 절반에 1/2을 더하면 정수가 나온다. 따라서 1+4k가 제곱수이기만 하면 된다. 즉, t가 파티션이 될 조건은 1+4k가 제곱수가 될 조건과 같다. 그럼 m보다 작은 k에 대해서 1+4k가 제곱수인지 조사하면 된다. 1+4k의 제곱근을 2n+1이라고 가정하자. 그럼 $1+4k=4n^2+4n+1$ 이므로 $k=n(n+1)$ 이 된다. 이 말은, $k=n(n+1)$조건을 만족하기만 하면 t는 파티션이 된다는 뜻이다. 그럼 m보다 작은 n(n+1)인 숫자들을 찾아내면 된다.
이제, t가 양의 정수(앞으로는 그냥 정수라고 하겠다)인 경우를 생각해 보자.
$2^t=\frac{1}{2} + \frac{1}{2}\sqrt{1+4k}$
여기에 k=n(n+1)을 대입해 보자.
$2^t = 1+ 2n+1 = 2(n+1)$
이렇게 식이 변했다. 앞에 있는 2를 떼어 내고도 t가 정수가 되기 위해서는 n+1 또한 2의 거듭제곱수이면 충분하다.
따라서 t가 perfect partition이 되기 위해서는 어떤 양의 정수 q에 대해서 $n=2^q-1$ 형태면 충분하다.
자, 이제 m에 대해 t가 정수가 되는 k가 몇개나 되는지 따져볼 차례다.
k=n(n+1)이었고, $n=2^q-1$ 형태였으므로, 이걸 다시 k에 대입하면
$k=4^q-2^q$
가 된다.
이제, q에 1부터 하나씩 대입해 가면서 문제에서 주어진 m이 k보다 작은 경우가 몇개나 되는지 보면 된다.
따라서, 다음의 부등식을 만족하는 최대의 q값을 구하면 된다.
$4^q -2^q \leq m$
정리하자면 다음과 같다.
1.n(n+1)이 m보다 작게 되는 양의 정수 n이 몇개인지 조사한다. 이 숫자를 A(m)라고 정의한다.
2.그러한 양의 정수 n중에서 n+1이 2의 거듭제곱수가 되는 경우가 몇개인지 조사한다. 이 숫자를 B(m)라고 한다.
3. P(m)=A(m)/B(m) 이다.
그런데, 반대로 생각해 보자. 어차피 k는 n(n+1)이 되기만 하면 되므로, $n=2^q-1$을 계산해서 q를 1씩 더하고, 그때마다 n이 어떻게 커지는지를 살펴보면 되지 않을까?
어쨌거나 이 문제를 풀게 된 알고리즘은 다음과 같다.
1. n을 계속해서 1씩 키워나간다.
2. n+1이 2의 거듭제곱수가 되면 q를 1만큼 증가시킨다.
3. q/n<1/12345가 되면 멈추고 n*(n+1)을 출력한다.
출력된 값이 m의 최소값이다.
덧붙임.
문제 해결하는 코드를 C로 짰는데 32비트 머신에서 쓸 수 있는 숫자의 자릿수가 너무 작아서 (답이 4294967296을 넘는 것 같음) 풀지 못하였다.
이건 뭐 페르마의 대정리도 아니고...-_-;;;;
결론적으로.
답이 32비트 머신에서 쓸 수 있는 숫자(4294967296)보다 많은 것은 사실이었다. 그래서 마지막 계산은 공학용 계산기를 썼다.
정답
RECENT COMMENT