개요

  • 이 문서는 [[CONCRETE-MATH]]책의 1장을 공부하며 메모한 것입니다.
  • 이 문서는 메모일 뿐이니 자세한 내용은 교재를 참고해야 합니다.

1.3 요세푸스 문제(THE JOSEPHUS PROBLEM)

1세기의 역사가 플라비우스 요세푸스(Flavius Josephus)의 이름을 딴 문제를 변형한 문제.

  • 제 1차 유대-로마 전쟁 중, 41명의 유대인 반역자들을 한 동굴에 모아놓았다.
  • 반역자들은 갇혀있기 싫어서 자살을 하기로 결심하였다.
  • 자살하는 방식은 다음과 같다.
    • 둥글에 원을 그리고 앉는다.
    • 원을 따라 두 번째 사람을 죽인다.
    • 모두가 죽을 때까지 이를 반복한다.
  • 그런데 두 사람(요세푸스와 그의 친구)은 죽고 싶지 않았다.

요세푸스와 친구는 원의 어느 위치에 있어야 살아남을 수 있을까?

최초에 n명이 원에 앉아 있을 때, 마지막에 살아남는 사람의 번호를 J(n)이라 하자.

그렇다면 위의 문제는 임의의 n에 대하여 J(n)의 값을 구하는 문제로도 볼 수 있다.

값을 미리 계산할 수 있다면, 살아남는 자리를 차지하여 죽지 않을 수 있다.

작은 사례부터 생각하자

n = 10 인 경우부터 생각해보자.

1 2 3 4 5 6 7 8 9 10
  • 1부터 세어나가며 죽인다고 할 때 죽이는 순서는 2, 4, 6, 8, 10, 3, 7, 1, 9 이다.
  • 따라서, J(10) = 5

추측 : J(10) = 5 이니까, \(J(n) = { n \over 2 }\)이 아닐까?

n이 작을 때 nJ(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 3 5 7 ... 2n - 3 2n - 1

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)의 값도 구할 수 있게 되었다.

\[\begin{align} J(20) & = 2J(10) - 1 \\ & = 2 \times 5 - 1 \\ & = 9 \\ \end{align}\]

n이 홀수인 경우

n이 홀수인 경우는 어떻게 될까?

  • 사람의 수가 2n + 1만큼 있다고 가정하자.
  • 일단 첫 루프에서는 2, 4, 6, 8, ... 2n 과 같이 모든 짝수 번호가 죽는다.
  • 그리고 마지막 2n + 1 번째 사람을 건너뛰게 되므로, 두 번째 루프에서는 1 이 가장 먼저 죽는다.

아무래도 두 번째 루프가 시작되고 1이 죽고 난 다음까지를 첫 번째 루프로 생각하는 쪽이 쉬울 것 같다.

그렇다면 새로 정의한 첫 번째 루프가 끝난 직후는 다음과 같을 것이다.

3 5 7 9 ... 2n - 1 2n + 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씩 증가한다.
  • n2의 거듭제곱일 때마다 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_m 2^m + b_{m-1} 2^{m - 1} + ... + b_1 2^1 + b_0 2^0\]

위의 n을 다음과 같이 이진수 전개하는 것도 생각해 볼 수 있는 일이다.

\[n = (b_m b_{m-1} ... b_{1} b_{0})_2\]
  • 단, 각 \(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\)  
    • 2ll << 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}\) 에 대해 생각해보자.
  • 이 추측은 틀린 가설이었다.
    • 이제는 해가 있으니 해를 사용하면 이 추측이 참인 경우를 판정 가능하다.
\[\begin{align} J(n) & = \frac{n}{2} \\ J(2^m + l) & = \frac{2^m + l}{2} \\ 2l + 1 & = \frac{2^m + l}{2} \\ 4l + 2 & = 2^m + l \\ 3l & = 2^m - 2 \\ l & = \frac{2^m - 2}{3} \\ \end{align}\]

즉, \(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)의 점화식은 다음과 같았다.

\[\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}\]

이를 일반화하기 위해 상수 \(\alpha, \beta, \gamma\)를 도입한 함수 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}\]

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을 대입해 보자.

  • 첫번째 식은 다음과 같이 정리된다.
\[\begin{align} f(1) & = \alpha \\ 1 & = \alpha \\ \end{align}\]
  • 두번째 식은 다음과 같다.
    • f(n)n이 무엇이건 간에 1을 리턴하므로, f(2n)1 이라는 점을 활용한다.
\[\begin{align} f(2n) & = 2f(n) + \beta \\ 1 & = 2 \cdot 1 + \beta \\ -1 & = \beta \\ \end{align}\]
  • 세번째 식은 다음과 같다.
\[\begin{array}{rl} f(2n + 1) & = 2f(n) + \gamma \\ 1 & = 2 \cdot 1 + \gamma \\ -1 & = \gamma \\ \end{array}\]

따라서, \(\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 인 경우를 생각해보자.

  • 첫번째 점화식은 다음과 같이 정리된다.
\[\begin{align} f(1) & = \alpha \\ 1 & = \alpha \\ \end{align}\]
  • 두번째 식은 다음과 같다.
\[\begin{align} f(2n) & = 2f(n) + \beta \\ 2n & = 2 \cdot n + \beta \\ 0 & = \beta \\ \end{align}\]
  • 세번째 식은 다음과 같다.
\[\begin{array}{rl} f(2n + 1) & = 2f(n) + \gamma \\ 2n + 1 & = 2 \cdot n + \gamma \\ 1 & = \gamma \\ \end{array}\]

따라서, \(\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)은 다음과 같이 볼 수 있다.
\[\begin{align} A(n) - B(n) - C(n) & = 1 \\ - A(n) + B(n) + C(n) & = -1 \\ B(n) & = A(n) - C(n) - 1 \\ 2^m -1 -l & = A(n) - C(n) - 1 \\ 2^m -l & = A(n) - C(n) \\ 2^m -l & = 2^m - l \\ \end{align}\]
  • C(n)은 다음과 같이 볼 수 있다.
\[\begin{align} A(n) + C(n) & = n; \\ A(n) + l & = n \\ 2^m + l & = n \\ \end{align}\]

일반화된 점화식에 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을 곱해주면 된다.

\[\begin{array}{r} n & = & ( \; 1 & 1 & 0 & 0 & 1 & 0 & 0 & )_2 & = 100 \\ \hline f(n) & = & ( \; 1 & 1 & -1 & -1 & 1 & -1 & -1 & )_2 & \\ & = & +64 & +32 & -16 & -8 & +4 & -2 & -1 & & = 74 \\ \end{array}\]

어떻게 이 방법이 비트 순환과 똑같은 결과를 내는 것일까?

비트가 3개인 모든 경우를 살펴보자.

  • 111 : 7인 경우
  • 110 : 6인 경우
  • 101 : 5인 경우
  • 100 : 4인 경우
7인 경우

7인 경우를 먼저 생각해보자.

\[\begin{array}{r} n & = & ( \; 1 & 1 & 1 & )_2 & = 7 \\ \hline f(n) & = & ( \; 1 & 1 & 1 & )_2 & \\ & = & 4 & 2 & 1 & & = 7 \\ \end{array}\]

7과 같이 비트가 1만 있는 경우는 0이 없으므로 빼는 숫자가 없어 값이 그대로 나온다.

비트 순환을 하나 마나 똑같은 결과이므로 비트 순환과 똑같다.

이는 7 외에도 3(\(11_2\)), 15(\(1111_2\)) 등등 \(2^x - 1\) 형태인 모든 숫자에 해당될 것이다.

6인 경우

이번에는 6인 경우를 생각해보자.

\[\begin{array}{r} n & = & ( \; 1 & 1 & 0 & )_2 & = 6 \\ \hline f(n) & = & ( \; 1 & 1 & -1 & )_2 & \\ & = & 4 & 2 & -1 & & = 5 \\ \end{array}\]
  1. 110 에서 1 을 빼면 101 이 된다.
  2. 110 => 101이 되었으므로 좌측 비트 순환과 똑같다.
5인 경우

이번에는 5인 경우를 생각해보자.

\[\begin{array}{r} n & = & ( \; 1 & 0 & 1 & )_2 & = 5 \\ \hline f(n) & = & ( \; 1 & -1 & 1 & )_2 & \\ & = & 4 & -2 & 1 & & = 3 \\ \end{array}\]
  1. 101 에서 10 을 빼면 011 이 된다.
  2. 101 => 011이 되었으므로 좌측 비트 순환과 똑같다.
4인 경우

이번에는 4인 경우를 생각해보자.

\[\begin{array}{r} n & = & ( \; 1 & 0 & 0 & )_2 & = 4 \\ \hline f(n) & = & ( \; 1 & -1 & -1 & )_2 & \\ & = & 4 & -2 & -1 & & = 1 \\ \end{array}\]
  1. 100 에서 1 을 빼면 011 이 된다.
  2. 011 에서 10 을 빼면 001 이 된다.
  3. 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}\]

dc를 보면 알 수 있겠지만, nd진법이고, f(n)c진법으로 생각하는 쪽이 계산이 편리하다.

\[f((b_m b_{m - 1} ... b_1 b_0)_d) = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0} )_c\]

f(19) 계산 예제

이제서야 1장의 마지막 예제를 이해할 수 있을 것 같다.

1장의 마지막 예제는 다음과 같은 점화식을 통해 f(19)를 계산하는 것이다.

\[\begin{array}{rll} f(1) & = 34; \\ f(2) & = 5; \\ f(3n) & = 10f(n) + 76, & for \; n \ge 1; \\ f(3n + 1) & = 10f(n) - 2, & for \; n \ge 1; \\ f(3n + 2) & = 10f(n) + 8, & for \; n \ge 1; \\ \end{array}\]
  • 19는 3의 배수 + 1 이니까, \(f(3n + 1) = 10f(n) - 2\)를 사용해 시도해보면 될 것 같다.
    • 3n + 1을 보면, d = 3 이다.
    • 10f(n) - 2를 보면, c = 10이다.
    • 그리고 1918 + 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}\).
  • [[CONCRETE-MATH]]