Fixed Points of the Josephus Function via Fractional Base Expansions

이 논문은 조세퍼스 함수 $J_3$의 고정점 수열과 중국인의 나머지 정리 간의 연관성을 규명하고, $3/2$ 기수법으로 표현된 두 연속된 고정점의 자릿수 패턴을 분석하여 그 전개식을 결정하는 재귀적 절차를 도출합니다.

핵심

1. 배경: "생존자 찾기" 게임 (요세푸스 문제)

상상해 보세요. 원탁에 사람들이 앉아 있고, "3 명마다 한 명씩 제거하자"는 규칙이 있습니다. (1, 2 는 넘기고 3 번은 퇴장). 이 과정을 마지막 한 명이 남을 때까지 반복합니다.

• 질문: "내가 살아남으려면 몇 번 자리 (번호) 에 앉아야 할까?"
• 해결책: 수학자들은 이 문제를 해결하는 공식 $J_3(n)$을 알고 있습니다. 하지만 $n$(사람 수) 이 엄청나게 커지면 공식을 직접 계산하는 게 너무 어렵습니다.

이 논문은 **"특정한 자리 (고정점)"**에 집중합니다. 즉, "사람 수가 $N$명일 때, 살아남는 사람이 바로 $N$번인 경우"를 찾는 것입니다. (예: 1 명일 때 1 번이 살아남음, 2 명일 때 2 번이 살아남음 등).

2. 핵심 발견 1: "중국인의 나뭇잎" (중국 나머지 정리)

연구자들은 이 생존자 번호들이 단순히 우연히 나오는 게 아니라, 두 가지 서로 다른 규칙을 동시에 만족하는 '수학적인 열쇠'라고 발견했습니다.

• 비유: 마치 자물쇠가 두 개의 다른 열쇠 (3 의 배수 규칙과 2 의 배수 규칙) 로만 열 수 있는 것처럼요.
• 중국 나머지 정리 (CRT): 고대 중국의 수학자들이 개발한 이 원리는 "서로 다른 규칙을 동시에 만족하는 숫자는 하나뿐이다"라고 말합니다.
• 의미: 연구자들은 이 '두 가지 규칙'을 이용해 다음 생존자 번호를 예측할 수 있는 공식을 세웠습니다.

3. 핵심 발견 2: "3/2 진법"이라는 새로운 언어

가장 흥미로운 부분은 숫자를 표현하는 방식을 바꾼 것입니다. 우리는 보통 10 진법 (0~9) 이나 2 진법 (0, 1) 을 쓰지만, 이 논문은 3/2 진법이라는 아주 특이한 언어를 사용했습니다.

• 비유: 우리가 숫자를 쌓아 올릴 때, 보통 10 개가 모이면 10 자리로 넘어갑니다. 하지만 이 '3/2 진법'은 2 개가 모이면 3 개로 변하는 이상한 세계입니다. (2 개의 동전이 모이면 3 개의 동전이 되는 마법 같은 세상).
• 새로운 규칙: 이 세계에서 숫자는 0, 1, 2 세 가지 숫자 (0, 1, 2) 만으로 표현됩니다.

4. 놀라운 패턴: "레고 블록 쌓기"

연구자들은 이 3/2 진법으로 생존자 번호들을 적어보니, 엄청난 패턴이 발견되었습니다.

• 패턴 설명:
  • 첫 번째 생존자 번호를 3/2 진법으로 쓰면: 2
  • 두 번째 생존자 번호는: 2 뒤에 1을 붙인 21
  • 세 번째는: 21 뒤에 0112 같은 무언가를 붙인 형태
• 핵심 메타포: 마치 레고 블록을 쌓는 것과 같습니다.
  • 이전 생존자 번호의 3/2 진법 숫자열은 기존 블록입니다.
  • 다음 생존자 번호는 그 기존 블록을 그대로 가져와서, 뒤에 새로운 블록들을 붙이는 것입니다.
  • 붙이는 블록의 모양 (1 개, 02, 0112 등) 은 두 생존자 사이에 '순수한 극단점'이 몇 개나 있는지에 따라 정해집니다.

5. 결론: 왜 이 연구가 중요한가?

이 논문은 단순히 숫자를 계산하는 방법을 넘어, 복잡한 퍼즐이 단순한 규칙 (레고 쌓기) 으로 이루어져 있음을 증명했습니다.

1. 예측의 용이성: 이전 생존자 번호만 알면, 뒤에 어떤 블록을 붙여야 할지 알 수 있어 다음 생존자 번호를 쉽게 구할 수 있습니다.
2. 새로운 시선: "3/2 진법"이라는 낯선 언어를 사용함으로써, 기존에 보이지 않던 숨겨진 패턴을 찾아냈습니다.
3. 미래 전망: 이 방법이 4 명마다 제거하는 문제 ($J_4$) 나 더 복잡한 상황에도 적용될 수 있을지, 그리고 이 패턴을 이용해 생존자 번호를 더 빠르게 계산할 수 있을지 연구의 문을 열었습니다.

한 줄 요약:

"복잡한 요세푸스 생존자 문제를 해결하기 위해, 연구자들은 3/2 진법이라는 새로운 언어를 개발했고, 그 안에서 생존자 번호들이 레고 블록처럼 규칙적으로 이어지는 패턴을 발견했습니다."

기술 요약

논문 요약: 분수 기수법 확장을 통한 요세푸스 함수의 고정점 연구

1. 연구 배경 및 문제 정의

• 요세푸스 문제 (Josephus Problem): $n$명의 사람이 원형 테이블에 앉아 있고, 1 번부터 시작하여 두 명을 건너뛰고 세 번째 사람을 제거하는 과정을 반복할 때 마지막 생존자의 위치를 찾는 고전적인 조합론 문제입니다.
• 요세푸스 함수 $J_3(n)$: 3 명마다 제거하는 경우 ($k=3$) 의 생존자 위치를 나타내는 함수입니다.
• 고정점 (Fixed Points): $J_3(n) = n$을 만족하는 정수 $n$을 고정점 ($n_p^{(\ell)}$) 이라고 정의합니다. 즉, $n$명이 있을 때 $n$번 자리에 앉으면 생존자가 됩니다.
• 연구 목적: $J_2$ (2 명마다 제거) 의 경우 고정점이 $2^{\ell-1}$로 명확한 이진법 패턴을 보이지만,$J_3$의 고정점들은 복잡한 재귀적 구조를 가집니다. 본 논문은$J_3$의 고정점 수열의 구조를 이해하고, 이를 중국인의 나머지 정리 (CRT) 와 기수 3/2 의 분수 기수법 (Fractional Base 3/2) 을 사용하여 체계적으로 설명하는 것을 목표로 합니다.

2. 방법론 (Methodology)

가. 중국인의 나머지 정리 (Chinese Remainder Theorem, CRT) 와의 연결

• 고정점 수열 $\{n_p^{(\ell)}\}$은 다음과 같은 재귀 공식으로 정의됩니다:
  $$n_p^{(\ell+1)} = \frac{3^{m_\ell}(3n_p^{(\ell)} + 2) - 2^{m_\ell}}{2^{m_\ell+1}}$$
  여기서 $m_\ell$는 $3n_p^{(\ell)} + 2$를 나누는 2 의 최대 거듭제곱 지수입니다.
• 이 식을 변형하면 $n_p^{(\ell+1)}$과 $n_p^{(\ell)}$이 서로소인 모듈로 $3^p$와$2^q$에 대한 선형 합동식 시스템을 만족함을 유도할 수 있습니다.
• 이를 통해 고정점들을 CRT 를 적용하여 해를 구하는 문제로 재정의하고, 베주 항등식 (Bézout's identity) 을 통해 모듈로 연산의 관계를 규명했습니다.

나. 기수 3/2 (Base 3/2) 분수 기수법 도입

• 기존에 알려진 기수 3/2 (숫자 0, 1 만 사용) 과는 다른, 숫자 집합 $D=\{0, 1, 2\}$를 허용하는 새로운 기수 3/2 표현법을 도입했습니다.
• 임의의 자연수 $N$을 다음과 같이 표현합니다:
  $$N = \frac{1}{2} \left[ d_k \left(\frac{3}{2}\right)^k + \dots + d_0 \right], \quad d_i \in \{0, 1, 2\}$$
• 이 표현을 계산하기 위한 4 단계 알고리즘을 제시했습니다:
  1. $2N_0 = 3N_1 + d_0$($d_0 \equiv 2N_0 \pmod 3$)
  2. $2N_i = 3N_{i+1} + d_i$를 반복하여$N_i$가 0 이 될 때까지 진행.
  3. 수학적 귀납법을 통해 표현의 유효성 증명.
  4. 알고리즘의 종료 보장 및 유일성 증명.

3. 주요 결과 및 발견 (Key Results)

가. 고정점 간의 패턴 발견 (Theorem 1)
기수 3/2 표현을 통해 $J_3$의 연속된 고정점 $n_p^{(\ell)}$과 $n_p^{(\ell+1)}$ 사이에는 놀라운 규칙성이 존재함이 증명되었습니다. $n_p^{(\ell)}$의 기수 3/2 표현이 $(\hat{d}_k \dots \hat{d}_0)_{3/2}$일 때, 다음 고정점 $n_p^{(\ell+1)}$의 표현은 다음과 같이 결정됩니다:

1. $m_\ell = 0$인 경우: 기존 표현의 오른쪽 끝에 **1**을 추가합니다.
   • 예: $(\dots \hat{d}_0 1)_{3/2}$
2. $m_\ell = 1$인 경우: 기존 표현의 오른쪽 끝에 **02**를 추가합니다.
   • 예: $(\dots \hat{d}_0 0 2)_{3/2}$
3. $m_\ell \ge 2$인 경우: 기존 표현의 오른쪽 끝에 0, 그 다음 $(m_\ell - 1)$개의 1, 그리고 마지막에 **2**를 추가합니다.
   • 예: $(\dots \hat{d}_0 \underbrace{0 1 \dots 1}_{m_\ell-1 \text{ 개}} 2)_{3/2}$

나. 자릿수 증가 규칙

• $n_p^{(\ell+1)}$의 기수 3/2 표현의 총 자릿수는 $n_p^{(\ell)}$의 자릿수보다 정확히 $m_\ell + 1$만큼 증가합니다.

다. 수치적 검증

• 표 3 에 제시된 바와 같이, $n_p^{(1)}$부터 $n_p^{(20)}$까지의 고정점들을 기수 3/2 로 변환했을 때 위 규칙이 완벽하게 성립함을 확인했습니다. 예를 들어, $m_\ell$의 값에 따라 끝자리 패턴이 1, 02, 012, 0112 등으로 규칙적으로 변합니다.

4. 의의 및 기여 (Significance)

• 구조적 통찰: $J_3$의 고정점들이 단순히 무작위적으로 생성되는 것이 아니라, 중국인의 나머지 정리와 기수 3/2 표현을 통해 매우 명확한 재귀적 디지털 패턴을 가진다는 것을 증명했습니다.
• 계산적 효율성: 고정점을 직접 계산하기 위해 복잡한 재귀 공식을 반복 적용할 필요 없이, 이전 고정점의 기수 3/2 표현과 $m_\ell$ 값만 알면 다음 고정점의 숫자열을 즉시 구성할 수 있는 알고리즘을 제시했습니다.
• 일반화 가능성: $J_2$의 경우 이진법 (Base 2) 에서 고정점이 $11\dots1$형태를 보인 것과 유사하게,$J_3$는 기수 3/2 에서 유사한 패턴을 보임으로써 요세푸스 함수의 일반화 ($J_k$) 에 대한 새로운 연구 방향을 제시했습니다.

5. 결론 및 향후 연구 방향

• 본 연구는 요세푸스 함수의 고정점 구조를 분수 기수법 관점에서 성공적으로 규명했습니다.
• 남은 과제:
  1. 임의의 $n$에 대해 $J_3(n)$을 직접 계산하기 위해 $n$의 기수 3/2 표현을 활용할 수 있는지 여부.
  2. $J_4$ (4 명마다 제거) 의 경우 기수 4/3 에서 유사한 재귀적 디지털 공식이 존재하는지 확인. ($J_4$는 두 가지 유형의 순수 고극점 (pure high extremal points) 을 가지므로 더 복잡한 인덱싱이 필요할 것으로 예상됨).

이 논문은 수론 (Number Theory) 과 조합론의 교차점에서 새로운 기수법 체계를 활용하여 고전적인 문제를 해결한 대표적인 사례로 평가됩니다.