수학의 세계에는 별별 희한한 수열들이 많다. 피보나치 수열이나 메르센 수처럼 이름 붙은 유명한 수열도 있지만, 해괴한 규칙에 따라 만들어지는 수열도 있고, 뭔가 다른 계산을 하다가 나왔는데 아직 그 정체가 밝혀지지 않은 수열도 있다. 이런 수열들 가운데 비교적 수학적 의미가 있다고 인정되는 것들을 모아놓은 웹사이트가 있다. 수학자 슬론(Neil James Alexander Sloane)이 만든 On-Line Encyclopedia of Integer Sequences, 줄여서 OEIS가 그것으로, 처음에는 슬론이 종이에 적어 가며 수집한 목록 정도였지만, 지금은 독립된 도메인으로, 내용도 체계적으로 정리되어 있으며, 항목 수만 25만 개가 넘는다. 현재는 OEIS Foundation에서 관리하고 있다.

슬론은 OEIS에 있는 수열 가운데 가장 좋아하는 것으로 레카만 수열(Recamán sequence)을 들고 있다. OEIS 분류 번호 A005132인 이 수열은 콜롬비아의 수학자 베르나르도 레카만 산토스(Bernardo Recamán Santos)가 제안한 것으로, 규칙이 좀 희한하다. 먼저 \(a_0=0\)으로 둔다. 그 다음부터는 \(a_n = a_{n-1}-n\)으로 계산하되, 만약 이 값이 양수가 아니거나, 양수이더라도 이전 항에 이미 나온 수라면 \(a_n = a_{n-1}+n\)으로 바꾸어 계산한다.

몇 개 항을 계산해 보면, \(n=1\)일 때, \(a_0-1 = -1\)은 양수가 아니므로, \(a_1 = a_0+1 = 1\)이 된다. 이어서, \(n=2\)일 때, \(a_1-2=-1\)이므로 \(a_2 = a_1+2=3\)이 된다. 같은 식으로, \(a_3 = a_2+3=6\)이다. \(n=4\)일 때, \(a_3-4=2\)인데, 이전 단계에서 \(2\)가 나타나지 않았으므로, \(a_4 = 2\)가 된다. 그 다음 항은 \(n\)을 더하여 \(a_5=a_4+5=7\), \(a_6=a_5+6=13\), \(a_7=a_6+7=20\)이고, 여덟 번째 항은 \(n=8\)을 빼서 \(a_8=a_7-8=12\)가 된다. 이런 식으로 70항까지 계산한 결과는 다음과 같다.

500항까지 구한 Recamán 수열

우선 생각해 볼 수 있는 질문이라면, 이 수열의 항이 모두 다를지 그렇지 않으면 같은 값이 나올 수 있을지일 것 같다. \(a_{n-1}-n\)이 이전 항에 나타나면 \(a_{n-1}+n\)을 계산하지만, \(a_{n-1}+n\)이 이전 항에 나타나는 경우에 대해서는 제한하지 않았기 때문이다. 이 질문은 간단히 답할 수 있다. 위에서 구한 항을 보면, \(a_{20}=a_{24}=42\)이므로 Recamán 수열에는 같은 값이 나올 수 있다. \(a_{18}=a_{26}=43\)도 위 표에서 찾을 수 있다.

이 수열에 중복되는 값이 나올 수는 있는 것은 쉽게 알 수 있겠는데, 이 수열이 모든 자연수를 만들어 낼 수는 있을까? 이 수열의 \(n\)번째 항은 앞 항과 \(n\) 차이가 나니까 그럴 것 같아 보이지는 않는다. 하지만 한편으로는 수열이 커졌다가 작아졌다가를 반복하는 형태여서 모든 자연수를 만들어 낼 수도 있을 것처럼 보인다. 어느 쪽이 참일까?

2001년에 AT&T의 앨런 윌크스(Allan Wilks)는 \(10^{15}\)번째 항까지 계산한 결과에 나타나지 않은 가장 작은 자연수가 \(852655 = 5 \times 31 \times 5501\)임을 발표하였다. 2010년에는 인텔의 컴퓨터 공학자인 벤자민 채핀(Benjamin Chaffin)이 \(10^{230}\)번째 항까지 계산해서, 여전히 \(852655\)가 나타나지 않음을 확인하였다. 과연 이 수는 Recamán 수열에 절대 나타나지 않는 수일까?