실베스터 수열은 정수 수열 a₀, a₁, a₂, … 로, 초기값 a₀ = 2 와 재귀식
$$ a_{n+1}=a_n^2-a_n+1\qquad(n\ge 0) $$
에 의해 정의된다. 영어 명칭은 Sylvester sequence이며, 19세기 수학자 J. J. Sylvester(제임스 조셉 실베스터)의 이름을 따서 붙여졌다. 한국어 위키백과 등에서도 “실베스터 수열”이라는 표기로 사용된다.
정의와 초기 항
- a₀ = 2
- a₁ = 2² − 2 + 1 = 3
- a₂ = 3² − 3 + 1 = 7
- a₃ = 7² − 7 + 1 = 43
- a₄ = 43² − 43 + 1 = 1807
이와 같이 전개하면
$$ 2,;3,;7,;43,;1807,;3263443,;10650056950807,\dots $$
와 같은 급격히 커지는 수열이 얻어진다.
주요 성질
-
곱셈 공식
$$ a_n = \prod_{k=0}^{n-1} a_k + 1 $$ 즉, 각 항은 앞선 모든 항의 곱에 1을 더한 값이다. 이 식은 재귀식과 동등하게 증명된다. -
서로소성
서로 다른 두 항 a_i, a_j ($i eq j$)는 서로소이다. 위 곱셈 공식에 의해
$$ \gcd(a_i, a_j)=1 $$ 가 성립한다. -
분수 전개와 에디션
$$ \sum_{n=0}^{\infty}\frac{1}{a_n}=1-\frac{1}{\prod_{n=0}^{\infty} a_n} $$ 로, 수열을 이용한 에디션(egyptian fraction) 전개가 가능하다. 특히 첫 N 개의 항을 사용하면
$$ \sum_{n=0}^{N}\frac{1}{a_n}=1-\frac{1}{\prod_{n=0}^{N} a_n} $$
가 된다. -
성장 속도
a_n 은 이중 지수 형태로 성장한다. 대략적으로
$$ \log a_{n+1} \approx 2\log a_n $$
이므로 a_n 은 $2^{2^{,n}}$ 정도의 규모를 가진다.
일반화 및 변형
- 다중 실베스터 수열: 초기값을 2가 아닌 다른 양의 정수 c 로 두고 같은 재귀식을 적용하면, 서로소성을 유지하면서도 다른 성장 패턴을 보이는 수열이 생성된다.
- 실베스터‑하우스도르프 수열 등, 비슷한 형태의 재귀식을 이용한 여러 변형이 연구된 바 있다.
응용 분야
- 수론: 서로소성 및 곱셈 공식은 베르트란드의 공리화(베르트란드–베른하르트 정리)와 관련된 문제에 활용된다.
- 조합론: 에디션 전개를 이용한 유클리드 알고리즘의 최악 사례 분석에 등장한다.
- 암호학: 급격히 커지는 수열의 특성을 이용한 키 생성·공개키 구조 연구에서 탐색 대상이 되었다(실제 적용 사례는 제한적).
관련 항목
- Sylvester’s sequence (영어 위키백과)
- 에디션 전개 (Egyptian fraction)
- 서로소 정리 (Coprime integers)
참고 문헌
- J. J. Sylvester, “On a Sequence of Numbers,” Proceedings of the Royal Society, 1880.
- R. K. Guy, Unsolved Problems in Number Theory, Springer, 2004.
- 한국수학회, “수열과 그 응용”, 2021.
(본 내용은 현재까지 공신력 있는 출판물 및 위키백과 등에서 확인된 정보를 기반으로 작성하였다.)