구체수학 01.재귀적인 문제들.03.요세푸스 문제
01.RECURRENT PROBLEMS
- 일러두기
- 1.3 요세푸스 문제(THE JOSEPHUS PROBLEM)
- Links
일러두기
- 이 문서는 [[/book/concrete-math]]책의 1장을 공부하며 메모한 것입니다.
- 이 문서는 메모일 뿐이니 자세한 내용은 교재를 참고해야 합니다.
1.3 요세푸스 문제(THE JOSEPHUS PROBLEM)
1세기의 역사가 플라비우스 요세푸스(Flavius Josephus)의 이름을 딴 문제를 변형한 문제.
- 제 1차 유대-로마 전쟁 중, 41명의 유대인 반역자들을 한 동굴에 모아놓았다.
- 반역자들은 갇혀있기 싫어서 자살을 하기로 결심하였다.
- 자살하는 방식은 다음과 같다.
- 둥글에 원을 그리고 앉는다.
- 원을 따라 두 번째 사람을 죽인다.
- 모두가 죽을 때까지 이를 반복한다.
- 그런데 두 사람(요세푸스와 그의 친구)은 죽고 싶지 않았다.
요세푸스와 친구는 원의 어느 위치에 있어야 살아남을 수 있을까?
최초에 n명이 원에 앉아 있을 때, 마지막에 살아남는 사람의 번호를 J(n)이라 하자.
그렇다면 위의 문제는 임의의 n에 대하여 J(n)의 값을 구하는 문제로도 볼 수 있다.
값을 미리 계산할 수 있다면, 살아남는 자리를 차지하여 죽지 않을 수 있다.
작은 사례부터 생각하자
n = 10 인 경우부터 생각해보자.
1부터 세어나가며 죽인다고 할 때 죽이는 순서는2, 4, 6, 8, 10, 3, 7, 1, 9이다.- 따라서,
J(10) = 5
추측 : J(10) = 5 이니까, \(J(n) = { n \over 2 }\)이 아닐까?
n이 작을 때 n과 J(n)과의 관계를 간단히 표로 정리해 보자.
| n | J(n) | 죽는 순서 |
|---|---|---|
| 1 | 1 | |
| 2 | 1 | 2 |
| 3 | 3 | 2, 1 |
| 4 | 1 | 2, 4, 3 |
| 5 | 3 | 2, 4, 1, 5 |
| 6 | 5 | 2, 4, 6, 3, 1 |
곰곰히 살펴보면 다음과 같은 사실을 알 수 있다.
J(3) = 3이고,J(4) = 1이므로 위의 추측은 틀렸다.2, 4, 6...과 같이 첫 루프에서는 짝수 번호가 전부 죽는다는 것을 알 수 있다.- 따라서
J(n)은 항상 홀수이다. n이 짝수이면, 첫 루프에서 짝수가 전부 죽고 인원수가 절반이 된다.- 즉 시작 인원 수가
2n인 경우, 첫 루프가 끝난 후의 인원 수는n이 된다.
- 즉 시작 인원 수가
n이 짝수인 경우
시작 인원 수가 2n인 경우가 쉬워보이니 이것부터 생각해보자.
1, 2, 3, 4... 가 1, 3, 5, 7... 이 된 셈이므로, 각 번호에 2를 곱하고 1을 뺀 것과 똑같은 모양이 되었다.
그렇다면 다음과 같이 표현할 수 있을 것이다.
\[J(2n) = 2J(n) - 1, \quad for \; n \ge 1\]이제 J(10)의 값이 5 라는 것을 알고 있기 때문에 J(20)의 값도 구할 수 있게 되었다.
n이 홀수인 경우
n이 홀수인 경우는 어떻게 될까?
- 사람의 수가
2n + 1만큼 있다고 가정하자. - 일단 첫 루프에서는
2, 4, 6, 8, ... 2n과 같이 모든 짝수 번호가 죽는다. - 그리고 마지막
2n + 1번째 사람을 건너뛰게 되므로, 두 번째 루프에서는1이 가장 먼저 죽는다.
아무래도 두 번째 루프가 시작되고 1이 죽고 난 다음까지를 첫 번째 루프로 생각하는 쪽이 쉬울 것 같다.
그렇다면 새로 정의한 첫 번째 루프가 끝난 직후는 다음과 같을 것이다.
1, 2, 3, 4... 가 3, 5, 7, 9... 가 된 셈이므로, 각 번호에 2를 곱하고 1을 더한 것과 같은 모양이 되었다.
그러므로, 짝수인 경우와 비슷하게 식을 표현할 수 있다.
\[J(2n+1) = 2J(n) + 1, \quad for \; n \ge 1\]점화식
위에서 얻어낸 식을 토대로 다음과 같은 점화식을 만들 수 있다.
\[\begin{array}{ll} J(1) & = 1; \\ J(2n) & = 2J(n) - 1, \quad for \; n \ge 1 \\ J(2n + 1) & = 2J(n) + 1, \quad for \; n \ge 1 \\ \end{array}\]python으로 표현하면 다음과 같다.
def J(n):
if n == 1:
return 1
if n % 2 == 0:
return 2 * J( n/2 ) - 1
else:
return 2 * J( (n-1)/2 ) + 1
이 점화식은 루프를 돌 때마다 n이 거의 절반으로 줄어들게 되므로 효율적이다.
그러나 생사가 달린 문제이므로 더 빠르게 계산할 수 있는 닫힌 형태의 해를 구하고 싶다. (재귀를 들어내고 \(O(1)\) 함수를 만들고 싶다)
해를 구해보자
점화식을 사용해 다음과 같은 표를 쉽게 찾아낼 수 있다.
## 다음 코드를 실행해도 볼 수 있다
for i in range(1, 17):
print(i, J(i))
| n | J(n) | |
|---|---|---|
| 1 | 1 | |
| 2 | 1 | 2J(1) - 1 |
| 3 | 3 | 2J(2) + 1 |
| 4 | 1 | 2J(2) - 1 |
| 5 | 3 | 2J(2) + 1 |
| 6 | 5 | 2J(3) - 1 |
| 7 | 7 | 2J(3) + 1 |
| 8 | 1 | 2J(4) - 1 |
| 9 | 3 | 2J(4) + 1 |
| 10 | 5 | 2J(5) - 1 |
| 11 | 7 | 2J(5) + 1 |
| 12 | 9 | 2J(6) - 1 |
| 13 | 11 | 2J(6) + 1 |
| 14 | 13 | 2J(7) - 1 |
| 15 | 15 | 2J(7) + 1 |
| 16 | 1 | 2J(8) - 1 |
J(n)은 홀수이며,1로 시작하고,2씩 증가한다.n이2의 거듭제곱일 때마다J(n)의 값은1이 된다.
따라서 n을 \(n = 2^m + l\)로 생각할 수 있다. (단, \(m \ge 0\) 이고, \(0 \le l \lt 2^m\))
그렇게 되면 각 n은 다음과 같이 대응된다.
| n | \(2^m + l\) | n | \(2^m + l\) | n | \(2^m + l\) | n | \(2^m + l\) |
|---|---|---|---|---|---|---|---|
| 1 | \(2^0 + 1\) | 2 | \(2^1 + 0\) | 4 | \(2^2 + 0\) | 8 | \(2^3 + 0\) |
| 3 | \(2^1 + 1\) | 5 | \(2^2 + 1\) | 9 | \(2^3 + 1\) | ||
| 6 | \(2^2 + 2\) | 10 | \(2^3 + 2\) | ||||
| 7 | \(2^2 + 3\) | 11 | \(2^3 + 3\) | ||||
| 12 | \(2^3 + 4\) | ||||||
| 13 | \(2^3 + 5\) | ||||||
| 14 | \(2^3 + 6\) | ||||||
| 15 | \(2^3 + 7\) |
점화식이 다음과 같으므로,
\[\begin{array}{ll} J(1) & = 1; \\ J(2n) & = 2J(n) - 1, \quad for \; n \ge 1 \\ J(2n + 1) & = 2J(n) + 1, \quad for \; n \ge 1 \\ \end{array}\]다음과 같은 식을 세울 수 있다.
\[J(2^m + l) = 2l + 1, \quad for \; m \ge 0 \; and \; 0 \le l \lt 2^ m\]이제 수학적 귀납법으로 이 식을 증명하자.
짝수인 경우
- \(2^m + l = 2k\) 인 경우를 생각해 보자.
- \(l\)은 홀수일 수 없으므로, 짝수이다.
\(J(2k) = 2J(k) - 1\) 이고, \(2^m + l = 2k\) 이므로, 다음과 같이 식을 꾸밀 수 있다.
\[\begin{align} J(2^m + l) & = 2J(\frac{2^m + l}{2}) - 1 \\ & = 2J(2^{m - 1} + \frac{l}{2}) - 1 \\ \end{align}\]그런데 \(J(2^m + l) = 2l + 1\) 이므로,
\(J(2^{m - 1} + \frac{l}{2}) = \frac{2l}{2} + 1\) 이다.
따라서 다음과 같은 결과가 나온다.
\[\begin{align} J(2^m + l) & = 2J(2^{m - 1} + \frac{l}{2}) - 1 \\ & = 2(\frac{2l}{2} + 1) - 1 \\ & = 2l + 1 \\ \end{align}\]이는 위에서 추측한 식과 맞아 떨어진다.
홀수인 경우
홀수인 경우는 책에 안 나오지만 해보도록 하자.
- \(2^m + l = 2k + 1\) 인 경우를 생각해 보자.
- \(l\)은 짝수일 수 없으므로, 홀수이다.
- \(J(2k + 1) = 2J(k) + 1\) 이고,
- \(2^m + l = 2k + 1\) 이고,
- \(k = \frac{2^m + l - 1}{2}\) 이므로,
다음과 같이 식을 꾸밀 수 있다.
\[\begin{align} J(2k + 1) & = 2J(k) + 1 \\ J(2^m + l) & = 2J(\frac{2^m + l - 1}{2}) + 1 \\ & = 2J(2^{m-1} + \frac{l - 1}{2}) + 1 \\ \end{align}\]그런데 \(J(2^m + l) = 2l + 1\) 이므로,
\(J(2^{m - 1} + \frac{l - 1}{2}) = (l - 1) + 1 = l\) 이다.
따라서 다음과 같은 결과가 나온다.
\[\begin{align} J(2^m + l) & = 2J(2^{m-1} + \frac{l - 1}{2}) + 1 \\ & = 2l + 1 \\ \end{align}\]이 또한 위에서 추측한 식과 맞아 떨어진다.
2진법으로 풀면 쉽게 풀린다?
n을 다음과 같이 표현할 수 있을 것이다.
위의 n을 다음과 같이 이진수 전개하는 것도 생각해 볼 수 있는 일이다.
- 단, 각 \(b_i\) 는
0또는1이다. - 단, 제일 앞 비트인 \(b_m\) 은
1이다.
한편, \(n = 2^m + l\) 이므로 다음과 같이 표현할 수 있다.
- \(n = (1 b_{m - 1} b_{m - 2} ... b_1 b_0)_2\)
- \(l = (0 b_{m - 1} b_{m - 2} ... b_1 b_0)_2\)
- \(l = n \; mod \; 2^m\) 이기 때문에, \(n\)의 제일 앞자리를 0 으로 바꾼 값이 \(l\)이다.
- \(2l = (b_{m - 1} b_{m - 2} ... b_1 b_0 0)_2\)
2l은l << 1과 같으므로, 제일 오른쪽에 0 을 추가해주면 된다.
- \(2l + 1 = (b_{m - 1} b_{m - 2} ... b_1 b_0 1)_2\)
\(J(n) = 2l + 1\) 이므로 다음과 같이 정리할 수 있다.
\[\begin{align} J(n) & = 2l + 1 \\ & = (b_{m - 1} b_{m - 2} ... b_1 b_0 1)_2 \\ & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ \end{align}\]그런데 \(n = (1 b_{m - 1} b_{m - 2} ... b_1 b_0)_2\) 이므로, 다음이 증명된다.
\[\begin{align} J(n) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ J((b_m b_{m - 1} b_{m - 2} ... b_1 b_0)_2) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ \end{align}\]즉, n을 왼쪽으로 1회 비트 순환시키면 J(n)이 나온다.
단, 가장 왼쪽 비트가 0 일 경우엔 가장 왼쪽 비트를 삭제해 주어서, 제일 앞 비트를 1로 유지해 주어야 한다.
아름답다.
놀라움을 음미하기 위해 몇 가지 경우를 생각해 보자.
n = 13인 경우13 = 8 + 4 + 1이므로,1101(2)이다.- 이를 회전시키면
1011(2) = 11이 나온다.
n = 100인 경우100 = 64 + 32 + 4이므로,1100100(2)이다.- 이를 회전시키면
1001001(2) = 64 + 8 + 1 = 73이다. - \(100 = 2^6 + 36\) 이므로, \(l = 36\) 이고, \(2l + 1\)에 의해
73이 맞다.
최초의 추측 J(n) = n/2 를 생각해보자
즉 함수 J(n)은 다음과 같은 작업을 한다.
n의 제일 왼쪽에 있는1을 가장 오른쪽으로 옮긴다.1을 옮긴 결과, 제일 왼쪽에0또는00...이 있다면 삭제한다.- 결과는 항상
1로 시작해야 하기 때문이다.
- 결과는 항상
문제는 어느 정도 풀었지만, 함수 J(n)을 재귀시키는 경우를 생각해보자.
- 함수
J(J(J(...J(n)...)))과 같이 재귀시키면, 충분히 많이 돌릴 경우0은 전부 사라지고1만 남게 될 것이다.
예를 들어 101101101101011(2)를 충분히 회전시키면 0이 전부 삭제되어 1111111111(2) = 1023이 남게 될 것이다.
- 이제 최초의 추측 \(J(n) = \frac{n}{2}\) 에 대해 생각해보자.
- 이 추측은 틀린 가설이었다.
- 이제는 해가 있으니 해를 사용하면 이 추측이 참인 경우를 판정 가능하다.
즉, \(l = \frac{2^m - 2}{3}\) 이 정수인 경우에 한하여 추측은 들어맞게 된다.
다음은 \(J(n) = \frac{n}{2}\) 를 만족시키는 몇몇 경우이다.
| m | \(l\) | \(n = 2^m + l\) | \(J(n) = 2l + 1 = \frac{n}{2}\) | n(이진수) |
|---|---|---|---|---|
| 1 | 0 | 2 | 1 | 10 |
| 3 | 2 | 10 | 5 | 1010 |
| 5 | 10 | 42 | 21 | 101010 |
| 7 | 42 | 170 | 85 | 10101010 |
- 이진수를 보면 흥미로운 패턴을 보인다.
일반화 : 레퍼토리법(repertoire method)
f(n) 으로 일반화해보자
이제 J(n)과 비슷한 함수를 만나게 되었을 때에도 쉽게 풀 수 있도록 J(n)함수를 일반화해보자.
J(n)의 점화식은 다음과 같았다.
이를 일반화하기 위해 상수 \(\alpha, \beta, \gamma\)를 도입한 함수 f(n)을 만들어 보자.
n 이 작은 경우에 대한 테이블도 만들어 보자.
\[\begin{array}{l|l} n & f(n) \\ \hline 1 & \alpha \\ \hline 2 & 2 \alpha + 1 \beta \\ 3 & 2 \alpha + \qquad 1 \gamma \\ \hline 4 & 4 \alpha + 3 \beta \\ 5 & 4 \alpha + 2 \beta + 1 \gamma \\ 6 & 4 \alpha + 1 \beta + 2 \gamma \\ 7 & 4 \alpha + \qquad 3 \gamma \\ \hline 8 & 8 \alpha + 7 \beta \\ 9 & 8 \alpha + 6 \beta + 1 \gamma \\ \end{array}\]- \(\alpha\)의 계수는
n미만의 가장 큰 2의 거듭제곱으로 보인다. - \(\beta\)의 계수는
1씩 감소해,0까지 가는 것 같다. - \(\gamma\)의 계수는
0에서 출발하여1씩 증가하는 것 같다.
발견한 특징들을 사용해 다음과 같이 표현해보자.
\[\begin{align} n & = 2^m + l \quad \text{(이전과 같다)} \\ f(n) & = A(n)\alpha + B(n)\beta + C(n)\gamma \\ \end{align}\]그리고 다음과 같은 추측을 할 수 있다.
식 1.14
\[\begin{align} A(n) & = 2^m \\ B(n) & = 2^m - 1 - l \\ C(n) & = l \\ \end{align}\]수학적 귀납법으로 이를 증명하는 것은 생략하자. (별로 배울 것이 없다고 한다)
대신, \(\alpha = 1, \beta = 0, \gamma = 0\) 인 경우에 한해 생각해보자.
\[\begin{align} A(1) & = 1; \\ A(2n) & = 2A(n), \quad for \; n \ge 1 \\ A(2n + 1) & = 2A(n), \quad for \; n \ge 1 \\ \end{align}\]그리고 다음의 사실도 알 수 있다.
\[\begin{align} A(n) & = 2^m \\ A(2^m + l) & = 2^m \\ \end{align}\]점화식에 f(n)을 적용해보자
\[\begin{array}{ll} f(1) & = \alpha ; \\ f(2n) & = 2f(n) + \beta, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \gamma, \quad for \; n \ge 1 \\ \end{array}\]f(n) = 1 인 경우
위의 점화식에 f(n) = 1을 대입해 보자.
- 첫번째 식은 다음과 같이 정리된다.
- 두번째 식은 다음과 같다.
f(n)은n이 무엇이건 간에1을 리턴하므로,f(2n)도1이라는 점을 활용한다.
- 세번째 식은 다음과 같다.
따라서, \(\alpha = 1, \; \beta = -1, \; \gamma = -1\) 이다.
이를 \(f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma\)에 적용해 보면, 다음과 같이 된다.
\[\begin{align} f(n) & = A(n) - B(n) - C(n) \\ & = 1 \\ \end{align}\]f(n) = n 인 경우
위에서 한 것과 비슷하게 f(n) = n 인 경우를 생각해보자.
- 첫번째 점화식은 다음과 같이 정리된다.
- 두번째 식은 다음과 같다.
- 세번째 식은 다음과 같다.
따라서, \(\alpha = 1, \; \beta = 0, \; \gamma = 1\) 이다.
이를 \(f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma\)에 적용해 보면, 다음과 같이 된다.
\[\begin{align} f(n) & = A(n) + C(n) \\ & = n \\ \end{align}\]종합
이것으로 증명은 끝났다.
결과를 종합하면 다음과 같다!
\[\begin{align} A(n) & = 2^m, \quad where \; n = 2^m + l \; and \; 0 \le l \lt 2^m; \\ A(n) - B(n) - C(n) & = 1; \\ A(n) + C(n) & = n; \\ \end{align}\]이러한 방식으로 점화식을 풀어내는 것을 레퍼토리법(repertoire method)이라 부른다.
레퍼토리법에서는 우선 알고 있는 해에 대한 일반적인 매개변수들의 설정들을 구한다. 그러면 우리가 풀 수 있는 특별한 경우들에 대한 레퍼토리가 마련된다. 그런 다음에는 특별한 경우들을 결합해서 일반적인 경우를 얻는다. 이를 위해서는 독립 매개변수 개수(지금 예에서는 \(\alpha, \, \beta, \, \gamma\) 세 개)만큼의 개별적인 특수해들이 필요하다.
일반식을 얻어낸 김에 식1.14를 확인해보자.
식 1.14는 다음과 같은 추측이었다.
\[\begin{align} A(n) & = 2^m \\ B(n) & = 2^m - 1 - l \\ C(n) & = l \\ \end{align}\]A(n)은 자명하므로 따로 확인할 필요가 없다.B(n)은 다음과 같이 볼 수 있다.
C(n)은 다음과 같이 볼 수 있다.
일반화된 점화식에 2진법 방법 적용하기
2진법으로 풀면 쉽게 풀린다에서 구했던 2진법 J 점화식을 다시 떠올려 보자.
\(b_m = 1\)일 때,
\[\begin{align} J(n) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ J((b_m b_{m - 1} b_{m - 2} ... b_1 b_0)_2) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ \end{align}\]2진법 방식의 일반화를 위해 다음과 같이 정의하자.
- \(\beta_0 = \beta\)
- \(\beta_1 = \gamma\)
점화식은 다음과 같았다.
\[\begin{array}{ll} f(1) & = \alpha ; \\ f(2n) & = 2f(n) + \beta, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \gamma, \quad for \; n \ge 1 \\ \end{array}\]여기에 \(\beta_0 = \beta\)과 \(\beta_1 = \gamma\)를 적용하면 다음과 같이 된다.
\[\begin{array}{ll} f(1) & = \alpha ; \\ f(2n + 0) & = 2f(n) + \beta_0, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \beta_1, \quad for \; n \ge 1 \\ \end{array}\]두번째와 세번째 점화식은 다음과 같이 하나로 합칠 수 있다.
\[f(2n + j) = 2f(n) + \beta_j, \quad for \; j = 0,1 \; and \; n \ge 1\\\]이 점화식을 2진법으로 전개해 보면 다음과 같다.
\[\begin{align} f((b_m b_{m-1} ... b_1 b_0)_2) & = 2f((b_m b_{m-1} ... b_3 b_2 b_1)_2) + \beta_{b_0} \\ & = 4f((b_m b_{m-1} ... b_3 b_2)_2) + \beta_{b_1} + \beta_{b_0} \\ & = 8f((b_m b_{m-1} ... b_3)_2) + \beta_{b_2} + \beta_{b_1} + \beta_{b_0} \\ & ... \\ & = 2^m f((b_m)_2) + 2^{m - 1} \beta_{b_{m-1}} + ... + 2\beta_{b_1} + \beta{b_0} \\ & = 2^m \alpha + 2^{m - 1} \beta_{b_{m-1}} + ... + 2 \beta_{b_1} + \beta_{b_0} \\ & = (\alpha \beta_{b_{m-1}} ... \beta_{b_1} \beta_{b_0})_2 \\ \end{align}\]\(\alpha\)가 제일 앞에 있는 이유는, 제일 앞의 \(b_m = 1 = \alpha\)이기 때문이다.
그리고 한참 위에서 작성했던 표를 (새로운 관점으로) 다음과 같이 작성할 수 있다.
\[\begin{array}{l|r} n & f(n) \\ \hline 1 & \alpha \\ \hline 2 & 2 \alpha + 1 \beta \\ 3 & 2 \alpha + 1 \gamma \\ \hline 4 & 4 \alpha + 2 \beta + 1 \beta \\ 5 & 4 \alpha + 2 \beta + 1 \gamma \\ 6 & 4 \alpha + 2 \gamma + 1 \beta \\ 7 & 4 \alpha + 2 \gamma + 1 \gamma \\ 8 & 8 \alpha + 4 \beta + 2 \beta + 1 \beta \\ 9 & 8 \alpha + 4 \beta + 2 \beta + 1 \gamma \\ \end{array}\]\(n = 100 = (1100100)_2\) 인 경우를 생각해 보자.
- \(\beta_0 = \beta\)
- \(\beta_1 = \gamma\)
일단 위와 같이 2진법으로 표기된 \(0 \Rightarrow \beta \,\)이고, 2진법으로 표기된 \(1 \Rightarrow \gamma \,\) 이므로
요세푸스 값 \(\alpha = 1, \; \beta = -1, \; \gamma = 1\) 을 적용해보면 다음과 같다.
\(\alpha\)와 \(\gamma\)가 공통적으로 이진법 1을 의미하고, \(\beta\)가 이진법 0을 의미하므로,
이진법 n을 십진법으로 바꿀 때 이진법 0이 있는 곳에 \(\beta\) 값인 -1을 곱해주면 된다.
어떻게 이 방법이 비트 순환과 똑같은 결과를 내는 것일까?
비트가 3개인 모든 경우를 살펴보자.
- 111 : 7인 경우
- 110 : 6인 경우
- 101 : 5인 경우
- 100 : 4인 경우
7인 경우
7인 경우를 먼저 생각해보자.
7과 같이 비트가 1만 있는 경우는 0이 없으므로 빼는 숫자가 없어 값이 그대로 나온다.
비트 순환을 하나 마나 똑같은 결과이므로 비트 순환과 똑같다.
이는 7 외에도 3(\(11_2\)), 15(\(1111_2\)) 등등 \(2^x - 1\) 형태인 모든 숫자에 해당될 것이다.
6인 경우
이번에는 6인 경우를 생각해보자.
- 110 에서 1 을 빼면 101 이 된다.
110=>101이 되었으므로 좌측 비트 순환과 똑같다.
5인 경우
이번에는 5인 경우를 생각해보자.
- 101 에서 10 을 빼면 011 이 된다.
101=>011이 되었으므로 좌측 비트 순환과 똑같다.
4인 경우
이번에는 4인 경우를 생각해보자.
100에서 1 을 빼면 011 이 된다.- 011 에서 10 을 빼면
001이 된다. 100=>001이 되었으므로 좌측 비트 순환과 똑같다.
일반화한 식을 좀 더 일반화해보자
위에서 알아낸 점화식은 다음과 같았다.
\[\begin{array}{rll} f(1) & = \alpha, & \\ f(2n + j) & = 2f(n) + \beta_j, & for \; j = 0,1 \; and \; n \ge 1\\ \end{array}\]이를 다음과 같이 좀 더 일반화해볼 수 있을 것이다.
\[\begin{array}{rll} f(j) & = \alpha_j, & for \; 1 \le j \lt d ; \\ f(dn + j) & = cf(n) + \beta_j, & for \; 0 \le j \lt d \; and \; n \ge 1\\ \end{array}\tag{1.17}\]d와 c를 보면 알 수 있겠지만, n은 d진법이고, f(n)은 c진법으로 생각하는 쪽이 계산이 편리하다.
f(19) 계산 예제
이제서야 1장의 마지막 예제를 이해할 수 있을 것 같다.
1장의 마지막 예제는 다음과 같은 점화식을 통해 f(19)를 계산하는 것이다.
- 19는
3의 배수 + 1이니까, \(f(3n + 1) = 10f(n) - 2\)를 사용해 시도해보면 될 것 같다.3n + 1을 보면,d = 3이다.10f(n) - 2를 보면,c = 10이다.- 그리고
19는18 + 1이니까 3진법으로201이다.
따라서 다음과 같이 전개할 수 있다.
\[\begin{array}{rlrrrrll} n & = & ( \; 2 & 0 & 1 & )_3 & = 19 \\ \hline f(n) & = & ( \; \color{red}{5} & \color{red}{76} & \color{red}{-2} & )_3 & \\ & = & \color{red}{5} \cdot 10^2 & \color{red}{76} \cdot 10 & \color{red}{-2} & & = 500 + 760 - 2 \\ & & & & & & = 1258 \\ \end{array}\]위의 5, 76, -2 는 다음과 같이 얻어낸 것이다.
- \(f(2) = \color{red}{5}\).
- \(f(3n + 0) = 10f(n) + \color{red}{76}\) 이므로, \(\beta_0 = \color{red}{76}\).
- \(f(3n + 1) = 10f(n) \color{red}{-2}\) 이므로, \(\beta_1 = \color{red}{-2}\).
Links
- [[/book/concrete-math]]