레카만 수열 — 모든 자연수가 등장하는가

$a(0)=0$에서 시작합니다. $n$번째 단계에서는 바로 앞 수에서 $n$을 빼 봅니다. 뺀 값이 0 이상이고 앞서 나온 적이 없으면 그 값을 쓰고, 그렇지 않으면 $n$을 더합니다.

규칙 한 줄: 뺄 수 있고 처음 나오는 값이면 빼고, 아니면 더합니다.

예를 들어 0에서는 1을 뺄 수 없어 1을 더하고, 다음에는 1에서 2를 뺄 수 없어 2를 더합니다. 이렇게 시작한 수열은 $0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, \ldots$입니다.

모든 0 이상의 정수가 언젠가 등장할까요?

베르나르도 레카만 산토스가 1991년 N. J. A. 슬론에게 보낸 수열로, 지금은 OEIS A005132에 실려 있습니다. “가능하면 빼고, 아니면 더한다”는 짧은 규칙이지만 어떤 수가 언제 등장하는지는 매우 복잡합니다. 2018년 Numberphile 영상은 항 사이를 반원으로 잇는 시각화를 널리 알렸습니다. 핵심 질문은 이 규칙이 0 이상의 정수를 하나도 빠뜨리지 않는가입니다.

OEIS의 2026년 2월 8일 계산 기록은 $10^{612}$번째 항까지 확인했지만, 852{,}655는 여전히 등장하지 않은 가장 작은 정수라고 보고합니다. 그렇다고 이 수가 영원히 등장하지 않는다는 뜻은 아닙니다. 유한한 계산은 “아직 나오지 않았다”만 보여 줄 뿐, 모든 정수가 결국 등장하는지 또는 어떤 수가 영원히 빠지는지는 아직 증명되지 않았습니다.