The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Each language version is independently generated for its own context, not a direct translation.

🎮 게임의 규칙: "가장 작은 보물을 찾아라"

이 게임은 아주 간단한 규칙으로 시작합니다.

먼저 숫자 1과 2를 적어둡니다. (시작 점)
이제부터는 **"이미 적힌 숫자들 중, 연속된 두 개 이상을 더해서 만들 수 있는 가장 작은 숫자"**를 찾아서 다음에 적습니다.
- 예: 1, 2 가 있습니다.
- 1+2=3 이 가능하니까 3을 적습니다. (1, 2, 3)
- 2+3=5, 1+2+3=6 가능. 4 는 만들 수 없으니 5를 적습니다. (1, 2, 3, 5)
- 3+5=8, 2+3+5=10 등 가능. 4, 6, 7 은 만들 수 없으니 6을 적습니다. (1, 2, 3, 5, 6)
- ...이렇게 계속 이어집니다.

이렇게 만들어지는 숫자 나열을 **수열 (Sequence)**이라고 합니다.
1, 2, 3, 5, 6, 8, 10, 11, 14, 16...

❓ 문제: "숫자 4 는 왜 사라졌을까?"

이 게임의 규칙을 따라가다 보면 이상한 점을 발견합니다.
숫자 4는 절대 등장하지 않습니다. 7, 9, 12, 13... 도 마찬가지입니다.
수학자들은 오랫동안 궁금해했습니다. "이 게임이 만들어내는 숫자들이 거의 모든 자연수를 포함할까, 아니면 영원히 빠지는 숫자들이 계속 생길까?"

대부분의 사람들은 "아마도 거의 다 포함되겠지?"라고 생각했습니다. 하지만 이 논문의 저자 탕 (Tang) 박사는 **"아니요, 빠지는 숫자는 무한히 많습니다!"**라고 증명했습니다.

🔍 증명 과정: "무한한 빈 공간"

저자는 이 수열을 분석하면서 두 가지 중요한 사실을 발견했습니다.

1. 숫자 사이의 간격이 점점 벌어진다
수열의 $n$ 번째 숫자를 $a_n$ 이라고 합시다. 만약 이 수열이 모든 숫자를 포함한다면, $a_n$ 은 거의 $n$ 과 같아야 합니다 (예: 10 번째 숫자가 10 이어야 함).
하지만 저자는 **"아니야, $a_n$ 은 $n$ 보다 점점 더 많이 커져. 그 차이 ( $a_n - n$ ) 는 시간이 지날수록 무한히 커진다"**라고 증명했습니다.

비유: 이 수열은 길을 걷는 사람인데, 걸을수록 발걸음 (숫자) 이 너무 커져서, 1, 2, 3... 이라는 표지판 사이사이의 **빈 공간 (빠진 숫자)**이 점점 더 넓어지는 것입니다. 결국 그 빈 공간은 영원히 메워지지 않습니다.

2. 2 의 거듭제곱의 함정
수학적으로 아주 큰 숫자 중에는 '2 의 거듭제곱' (2, 4, 8, 16, 32...) 이 있습니다. 이 논문은 이 수열이 만들어내는 규칙상, 아주 큰 2 의 거듭제곱 숫자들은 연속된 숫자들의 합으로 만들기가 매우 어렵다는 점을 이용했습니다. 마치 특정 모양의 퍼즐 조각 (2 의 거듭제곱) 은 이 게임의 규칙상 절대 끼워 넣을 수 없는 구멍이 있다는 것을 수학적으로 증명해낸 것입니다.

📈 얼마나 빠르게 커질까? (상한선)

저자는 단순히 "빠지는 숫자가 많다"는 것뿐만 아니라, **"이 수열이 얼마나 빠르게 커지는지"**에 대한 숫자도 계산했습니다.
수열이 너무 느리게 커지면 모든 숫자를 포함할 수 있고, 너무 빠르게 커지면 빈 공간이 너무 많아집니다.
저자는 이 수열이 $n$ 의 약 1.666 배 (정확히는 $n^{4175/2506}$ ) 정도까지 커질 수 있다는 상한선을 구했습니다.

비유: 이 게임의 숫자가 자라나는 속도가 "개구리 점프"처럼 너무 느리지도, "폭포수"처럼 너무 빠르지도 않은, 아주 특정한 중간 속도를 가진다는 것을 계산해낸 것입니다.

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

오래된 의문 해결: 1970 년대부터 수학자들이 궁금해했던 이 수열의 성질을 완전히 해결했습니다. (OEIS 라는 수학 백과사전의 오래된 추측을 깨뜨림)
무한한 결손: 이 수열은 비록 규칙적으로 만들어지지만, 영원히 빠지는 숫자들이 무한히 많다는 것을 증명했습니다. 즉, "모든 숫자를 다 채울 수 있는 완벽한 수열"은 아닙니다.
새로운 발견: 이 연구는 단순히 하나의 수열을 넘어서, 비슷한 규칙을 가진 다른 수열들에도 적용될 수 있는 일반적인 원리를 제시했습니다.

💡 한 줄 요약

"이 수열은 숫자를 하나씩 채워나가는 게임처럼 보이지만, 실제로는 계속해서 빈 공간 (빠진 숫자) 을 만들어내며 무한히 커지는 놀라운 성질을 가지고 있었습니다. 저자는 이 '빈 공간'이 영원히 사라지지 않는다는 것을 수학적으로 증명했습니다."

이 논문은 복잡한 수학 공식 뒤에 숨겨진 수열의 본질적인 성질을 찾아낸, 매우 우아하고 중요한 발견입니다.

Each language version is independently generated for its own context, not a direct translation.

논문 개요

이 논문은 호프스타터 (Hofstadter) 가 제기한 유명한 자기 생성 수열 (self-generating sequence) 의 점근적 행동에 관한 문제를 해결합니다. 특히, 이 수열이 양의 정수 전체를 포함하는지, 아니면 무한히 많은 정수를 생략하는지에 대한 OEIS (A005243) 의 추측을 증명하고, 수열의 성장 속도에 대한 다항식 상한을 제시합니다.

1. 문제 정의 및 배경

수열의 정의: 초기값 $a_1=1, a_2=2$ $a_{1} = 1, a_{2} = 2$ 로 시작하며, $k \ge 3$ $k \geq 3$ 일 때 $a_k$ $a_{k}$ 는 $a_{k-1}$ $a_{k - 1}$ 보다 크면서 이전 항들의 연속된 두 개 이상의 합으로 표현될 수 있는 가장 작은 정수로 정의됩니다.
- 수열의 시작: 1, 2, 3, 5, 6, 8, 10, 11, 14, 16, 17, 18, 19, 21, 22, 24, 25, 29, 30, 32, ...
- 생략된 수: 4, 7, 9, 12, 13, 15, 20, ...
주요 질문 (Problem 1.1): 이 수열 $(a_n)$ 의 점근적 행동은 무엇인가?
추측 (Conjecture 1.2): 이 수열은 무한히 많은 양의 정수를 생략한다. (즉, 수열이 모든 양의 정수를 포함하지 않는다.)

2. 주요 기여 및 결과

가. 질적 결과 (Qualitative Result): 무한한 생략의 증명

저자는 임의의 유한한 초기 시드 (seed) 에서 시작하는 일반적인 자기 생성 수열에 대해 다음을 증명했습니다.

정의: $b_n = a_n - n$ 으로 정의합니다. 이는 $n$ 번째 항이 인덱스보다 얼마나 큰지를 나타냅니다.
정리 1.4: 모든 $n \ge s$ (초기 시드 길이) 에 대해 시퀀스 $(b_n)$ 은 단조 증가하며,且有한하지 않습니다 (unbounded). 즉, $b_n \to \infty$ 입니다.
결과 (Corollary 1.5): $a_n = n + \omega(1)$ 입니다. 이는 $a_n$ 이 $n$ 보다 훨씬 빠르게 증가함을 의미하며, 결과적으로 수열이 $[1, a_n]$ 구간 내에서 생략하는 정수의 개수가 무한히 증가함을 보여줍니다.
의의: 이는 OEIS A005243 의 추측을 완전히 증명하여, 이 수열이 "대부분"의 정수를 포함하는 것처럼 보이지만 실제로는 무한히 많은 정수를 빠뜨린다는 사실을 확정지었습니다.

나. 양적 결과 (Quantitative Result): 성장 속도의 상한

전통적인 수열 ( $a_1=1, a_2=2$ ) 에 대해 구체적인 상한을 제시했습니다.

정리 1.6: 임의의 $\epsilon > 0$ 에 대해 상수 $C_\epsilon$ 이 존재하여 모든 $n$ 에 대해 다음이 성립합니다.
$a_n \ll_\epsilon n^{4175/2506 + \epsilon}$
(약 $n^{1.666...}$ 의 다항식 성장)
이는 해당 수열의 성장 속도가 선형 ( $n$ ) 보다 빠르지만, 지수적이지는 않음을 보여주는 첫 번째 다항식 상한입니다.

3. 방법론 (Methodology)

논문은 크게 두 가지 단계로 나뉘어 증명됩니다.

단계 1: 질적 하한 증명 (Section 3)

선형 꼬리 (Linear Tail) 가정의 모순: 만약 $b_n$ 이 유계 (bounded) 라면, 충분히 큰 $n$ 에서 $a_n = n + B$ (선형) 형태가 되어야 함을 보입니다.
2 의 거듭제곱과 디오판토스 방정식: 선형 꼬리가 존재한다고 가정하면, 충분히 큰 $2^r $이 수열의 항이 되어야 합니다. 이를 연속된 항의 합으로 표현하면$ 2^r = C + \sum_{j=T}^{v} j $형태의 방정식이 도출됩니다. 이는$ v^2 + v + E = 2^k$ 형태의 디오판토스 방정식으로 귀결됩니다.
Schinzel-Tijdeman 정리 활용: Schinzel 과 Tijdeman 의 결과 (Corollary 2.3) 에 따르면, $v^2 + v + E = 2^k$ ( $k>2$ ) 는 유한개의 정수 해만 가집니다. 그러나 수열의 정의상 무한히 많은 $2^r $이 존재해야 하므로 모순이 발생합니다. 따라서$ b_n$은 무한히 커야 합니다.

단계 2: 양적 상한 증명 (Section 4)

표현 가능한 정수의 집합: 수열의 항들은 "연속된 항들의 합"으로 표현 가능한 정수들을 오름차순으로 나열한 것과 동일함을 보입니다.
볼록 집합 (Convex Set) 과 차이 집합:
- 부분합 집합 $S_m = \{s_0, s_1, \dots, s_m\}$ (여기서 $s_i = \sum_{j=1}^i a_j$ ) 은 볼록 집합임을 보입니다.
- 연속된 항의 합은 이 부분합 집합의 차이 집합 ( $S_m - S_m$ ) 의 원소로 표현됩니다.
Bloom 의 차이 집합 하한 (Theorem 4.6): 유한 볼록 집합 $A$ 에 대해 차이 집합의 크기 $|A-A|$ 는 $|A|^{6681/4175 - \eta}$ 보다 큽니다 (Bloom 의 최근 결과).
재귀적 상한 유도:
1. 표현 가능한 정수의 개수 $|R_m|$ 이 $m^\delta$ ( $\delta \approx 1.6$ ) 만큼 빠르게 증가함을 보입니다.
2. 이 증가율을 수열의 성장 $a_n$ 에 대입하여 재귀 부등식 $a_n \le C n^\alpha a_{\lceil C n^\alpha \rceil}$ 을 유도합니다.
3. 이 재귀식을 반복 적용하여 최종적으로 $a_n \ll n^{\alpha/(1-\alpha)}$ 형태의 다항식 상한을 얻습니다. 여기서 $\alpha = 1/\delta$ 이므로 지수는 $4175/2506$이 됩니다.

4. 의의 및 결론

추측 해결: 호프스타터 수열이 무한히 많은 정수를 생략한다는 오랜 추측을 해결했습니다.
성장 속도: 수열이 선형 ( $n$ ) 보다 빠르게 자라지만, 그 속도가 다항식 범위 내에 있음을 보였습니다.
남은 과제: 현재 증명된 상한 ( $n^{1.666}$ ) 과 실제 수치적 관측 ( $n^{1.33}$ 부근, 즉 $b_n \approx n^{1/3}$ ) 사이에는 여전히 간극이 있습니다. 저자는 볼록 집합의 차이 집합 크기에 대한 Erdős-Hegyvári 추측 ( $|A-A| \gg |A|^{2-o(1)}$ ) 이 참이라면 상한이 $n^{1+o(1)}$ 로 개선될 수 있음을 언급했으나, 현재 방법론으로는 선형 상한 ( $O(n)$ ) 을 증명하기 어렵다고 결론지었습니다.

이 논문은 자기 생성 수열의 구조를 이해하는 데 중요한 진전을 이루었으며, 가법 조합론 (additive combinatorics) 과 정수론의 기법을 결합하여 구체적인 수열의 행동을 분석한 사례로 의미가 큽니다.