라이크렐 수

라이크렐 수(Lychrel number)는 어떤 자연수와 그 수를 뒤집은 수를 더하고 이 수가 대칭수가 되지 않으면 이를 반복하는 과정을 거쳤을 때, 결코 대칭수가 되지 않는 수이다. 이 과정은 이와 관련된 대표적인 수인 196을 따서 196-알고리즘 또는 회문 알고리즘이라고 부른다. 십진법에서는 아직 어떠한 라이크렐 수도 발견되지 않았지만, 196를 포함한 여러 수들을 라이크렐 수로 추측하고 있다.^[1] '라이크렐(Lychrel)'이라는 명칭은 웨이드 반 랜딩 엄(Wade Van Landingham)이 그의 여자친구의 이름인 'Cheryl'의 애너그램으로 만들었다.^[2]

회문 알고리즘

회문 알고리즘은 어떤 수와 그 수를 뒤집은 수의 합을 생성한다. 예를 들어 56 + 65 = 121이고, 165 + 561 = 726이다.

어떤 수들은 몇 번의 회문 알고리즘을 거치면 바로 대칭수가 되어 라이크렐 수가 아니다. 모든 한 자리 수와 두 자리 수는 회문 알고리즘을 거치면 대칭수가 된다.

10000 이하의 수들 중 약 80%는 4단계 이하의 과정만으로 대칭수가 되고, 약 90%는 7단계 이하의 과정으로 대칭수가 된다. 라이크렐 수가 아닌 수로는 다음 예시들이 있다.

• 56은 한 번의 과정으로 대칭수가 된다 : 56 + 65 = 121 .
• 57은 두 단계 후에 대칭수가 된다 : 57 + 75 = 132, 132 + 231 = 363 .
• 59는 세 단계 후에 대칭수가 된다 : 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111
• 89는 대칭수 8,813,200,023,188에 도달하기 위해 예외적으로 많은 24단계^{[깨진 링크(과거 내용 찾기)]}(대칭수가 되는 10000 이하의 수들 중 가장 많은 횟수)를 거쳐야 한다.
• 10,911은 55단계^{[깨진 링크(과거 내용 찾기)]} 후에 대칭수 4668731596684224866951378664 (28 자리)에 도달한다.
• 12,000,700,000,025,339,936,491는 288단계 후에 142자리의 대칭수 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544에 도달하며, 이는 현재 가장 늦게 대칭수에 도달하는 수이다. 이 수는 OEIS A326414에 등록되었다.

가장 작은 라이크렐 수의 후보는 196이다. 라이크렐 수를 뒤집은 수 또한 라이크렐 수이다.

회문 알고리즘의 정의

자연수 ${\displaystyle n}$에 대해 ${\displaystyle b}$진법(${\displaystyle b>1}$)에서의 라이크렐 함수 ${\displaystyle F_{b}:\mathbb {N} \rightarrow \mathbb {N} }$를 다음과 같이 정의한다.

${\displaystyle F_{b}(n)=n+\sum _{i=0}^{k-1}d_{i}b^{k-i-1}}$

여기서 ${\displaystyle k=\lfloor \log _{b}{n}\rfloor +1}$는 수의 ${\displaystyle b}$진법에서의 자릿수이다. 또한

${\displaystyle d_{i}={\frac {n{\bmod {b^{i+1}}}-n{\bmod {b}}^{i}}{b^{i}}}}$

는 각 자릿수의 값이다. ${\displaystyle F_{b}^{i+1}(n)=2F_{b}^{i}(n)}$를 만족시키는 자연수 ${\displaystyle i}$가 존재하지 않는 경우 ${\displaystyle n}$은 라이크렐 수이다. ${\displaystyle F^{i}}$는 ${\displaystyle F}$의 ${\displaystyle i}$번째 단계 수이다.

미해결 난제

다른 기수법(이진법과 십육진법과 같이 2의 거듭제곱을 밑으로 하는 진법)에서 특정 숫자는 회문 알고리즘을 거친 후에도 대칭수가 되지 않음을 증명할 수 있다.^[3] 그러나 현재 10진법에서는 196을 포함한 다른 수들에 대해 라이크렐 수임이 증명되지 않았다. 라이크렐 수의 후보로는 다음 수들이 있다.(OEIS의 수열 A023108)

196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997.

볼드체로 된 수는 근원 라이크렐 수로 추정하는 수이다. Jason Doucette, Ian Peters과 Benjamin Despres은 컴퓨터로 다른 라이크렐 수 후보를 발견하였으며, 17자리 미만의 근원 라이크렐 수 후보를 간추렸다.^[4] Wade Van Landingham의 사이트에서는 각 자릿수에서의 총 근원 라이크렐 수의 개수를 보여준다.^[5]

196의 라이크렐 수 판별

가장 작은 라이크렐 수 후보인 196(십진법)에 대해 여러 계산시도가 있었다.

John Walker는 1987년 8월 12일 Sun 3/260 워크스테이션을 사용하여 196 대칭수가 되는지 계산하기 위해 수를 뒤집고 더하는 단계를 수행한 후에 각 단계마다 대칭수인지 판별하는 C 프로그램을 작성하였다. 프로그램은 백그라운드에서 실행되었으며, 약 3년간의 실행 후 1990년 5월 24일에 종료되었다. 종료 시점에서 196은 2,415,836번의 단계를 거쳐 백만 자리 수가 되었지만, 모든 단계에서 대칭수가 되지 않았다.

1995년 Tim Irvin과 Larry Simkins는 다중 처리 컴퓨터를 사용하여 대칭수를 찾지 못하고 3개월 만에 200만 자리에 도달하였다. Jason Doucette는 2000년 5월에 1,250만 자리에 도달하였다. Wade VanLandingham은 Jason Doucette의 프로그램을 사용하여 1,300만 자리에 도달하였으며, 2006년 5월 1일에 3억 자리에 도달하였다. 2011년 Romain Dolbeau는 분산 컴퓨팅을 사용하여 413,930,770자리에 도달하였으며, 2015년 2월 십억 자리를 넘어섰다.^[6] 196에 대해 진행했을 때 현재까지 대칭수는 나타나지 않았다.

196 외의 다른 라이크렐 수 후보인 879, 1997, 7059도 많은 단계까지 계산되었으며, 대칭수가 나타나지 않은 채 수백만 단계까지 진행되었다.^[7]

다른 기수법에서의 결과

2진법 수 10110(십진법에서는 22)는 라이크렐 수임이 증명되었다. 이 수는 4단계 후에 10110100, 8단계 후에 1011101000, 12단계 후에 101111010000이 되며, 일반적으로 4n단계 후에 10111···11101000···000(0과 1이 각각 n+3개만큼 있다.)으로 표현되는 수가 된다. 10110를 포함하여 이 수에 회문 알고리즘을 적용하여 얻은 수들 또한 라이크렐 수이다.

11, 17, 20, 26 및 2의 거듭제곱을 밑으로 하는 진법에서는 라이크렐 수가 존재함이 입증되었다.^[8][9] 다음은 b진법에서의 가장 작은 라이크렐 수 또는 라이크렐 수로 추정하는 수를 나열한 표이다.

b	b진법에서의 가장 작은 라이크렐 수 (또는 라이크렐 수로 추정하는 수)
2	10110 (22)
3	10211 (103)
4	10202 (290)
5	10313 (708)
6	4555 (1079)
7	10513 (2656)
8	1775 (1021)
9	728 (593)
10	196 (196)
11	83A (1011)
12	179 (237)
13	12CA (2701)
14	1BB (361)
15	1EC (447)
16	19D (413)
17	B6G (3297)
18	1AF (519)
19	HI (341)
20	IJ (379)
21	1CI (711)
22	KL (461)
23	LM (505)
24	MN (551)
25	1FM (1022)
26	OP (649)
27	PQ (701)
28	QR (755)
29	RS (811)
30	ST (869)

같이 보기

• 수학의 미해결 문제 목록
• 대칭수

각주

1. O'Bryant, Kevin (2012년 12월 26일). “Reply to Status of the 196 conjecture?”. 《Math Overflow》. 
2. “FAQ”. 2006년 12월 1일에 원본 문서에서 보존된 문서. 
3. Brown, Kevin. “Digit Reversal Sums Leading to Palindromes”. 《MathPages》. 
4. VanLandingham, Wade. “Lychrel Records”. 《p196.org》. 2016년 4월 28일에 원본 문서에서 보존된 문서. 2011년 8월 29일에 확인함. 
5. VanLandingham, Wade. “Identified Seeds”. 《p196.org》. 2016년 4월 28일에 원본 문서에서 보존된 문서. 2011년 8월 29일에 확인함. 
6. Dolbeau, Romain. “The p196_mpi page”. 《www.dolbeau.name》. 2015년 2월 11일에 원본 문서에서 보존된 문서. 2020년 7월 22일에 확인함. 
7. “Lychrel Records”. 2003년 12월 5일에 원본 문서에서 보존된 문서. 2016년 9월 2일에 확인함. 
8. “Digit Reversal Sums Leading to Palindromes”. 
9. “Letter from David Seal”. 2013년 5월 30일에 원본 문서에서 보존된 문서. 2017년 3월 8일에 확인함.