라이크렐 수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 회문 알고리즘 (리크렐 프로세스)
- 2.1. 회문 알고리즘의 정의
3. 10진법에서의 라이크렐 수
- 3.1. 196 문제
- 3.2. 스레드, 시드 수, 친족 수
4. 다른 진법에서의 라이크렐 수
- 4.1. 각 진법에서의 가장 작은 라이크렐 수 (또는 후보)
5. 음의 정수로의 확장
참조

1. 개요

라이크렐 수는 어떤 수와 그 수를 뒤집은 수의 합을 반복적으로 계산하는 회문 알고리즘을 적용했을 때, 회문수(대칭수)가 되지 않는 수를 의미한다. 10진법에서는 라이크렐 수의 존재가 아직 증명되지 않았으며, 196이 가장 작은 라이크렐 수 후보로 알려져 있다. 196이 라이크렐 수인지 판별하는 문제는 '196 문제'로 불리며, 현재까지 해결되지 않았다. 2진법을 포함한 다른 진법에서는 라이크렐 수가 존재함이 증명되었다. 라이크렐 수와 관련된 개념으로는 스레드, 시드 수, 친족 수가 있다.

더 읽어볼만한 페이지

수론의 미해결 문제 - 오일러-마스케로니 상수
오일러-마스케로니 상수 $\gamma$ 는 조화급수와 자연로그 함수의 차이의 극한으로 정의되는 수학 상수로, 감마 함수, 리만 제타 함수 등 다양한 수학적 개념과 관련되어 있으며 유리수인지 무리수인지 밝혀지지 않은 미해결 문제이다.
수론의 미해결 문제 - 리만 가설
리만 가설은 리만 제타 함수의 자명하지 않은 모든 영점의 실수부가 1/2이라는 추측으로, 힐베르트 문제와 클레이 수학 연구소의 밀레니엄 문제 중 하나이며 정수론과 복소해석학을 연결하는 다양한 수학적 명제들과 동치이다.

라이크렐 수

2. 회문 알고리즘 (리크렐 프로세스)

리크렐 프로세스(Lychrel process^eng) 또는 회문 알고리즘은 어떤 수와 그 수의 자릿수를 뒤집어 만든 수를 더하는 과정을 반복하는 것이다. 예를 들어, 56에 이 과정을 적용하면 56 + 65 = 121이 되고, 125에 적용하면 125 + 521 = 646이 된다.

대부분의 수는 이 과정을 몇 번 반복하면 회문이 되며, 이런 수는 라이크렐 수가 아니다. 모든 한 자리 수와 두 자리 수는 결국 회문이 된다. 10,000 미만의 수 중 약 80%는 4단계 이내에, 약 90%는 7단계 이내에 회문이 되는 것으로 알려져 있다. 라이크렐 수가 아닌 수의 예시는 다음과 같다.

시작 수	단계 수	최종 회문 (또는 중간 과정)
56	1	56 + 65 = 121
57	2	57 + 75 = 132, 132 + 231 = 363
59	3	59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111
89	24	8,813,200,023,188 (10,000 미만 수 중 회문 도달까지 가장 많은 단계)
10,911	55	466,873,159,668,422,486,695,137,866,4 (28자리)

일부 수는 회문이 되기까지 매우 많은 단계를 거치기도 하며, 회문 도달까지 가장 많은 단계를 필요로 하는 수에 대한 기록 갱신이 이루어지고 있다.

이 과정을 아무리 반복해도 회문이 되지 않는다고 추정되는 수를 '''라이크렐 수'''라고 한다. 현재까지 회문이 된다는 것이 증명되지 않은 가장 작은 수는 196이며, 이것이 가장 작은 라이크렐 수 후보이다. 또한, 0으로 끝나지 않는 라이크렐 수의 자릿수를 뒤집어 만든 수도 라이크렐 수이다.

2. 1. 회문 알고리즘의 정의

자연수

n

과 b진법(

b > 1

)에 대해 '''라이크렐 함수'''

F_{b} : \mathbb{N} \rightarrow \mathbb{N}

는 다음과 같이 정의된다.^[1]^[2]

:

F_{b}(n) = n + \sum_{i = 0}^{k - 1} d_i b^{k - i - 1}

여기서

k = \lfloor \log_{b}{n} \rfloor + 1

는 수

n

의

b

진법에서의 자릿수이며,

:

d_i = \frac{n \bmod{b^{i+1}} - n \bmod b^i}{b^i}

는 각 자릿수의 값이다. 즉, 라이크렐 함수는 주어진 수

n

과 그 수의 자릿수를 뒤집어 만든 수를 더하는 연산을 수행한다. 예를 들어, 10진법에서 56에 라이크렐 함수를 적용하면

F_{10}(56) = 56 + 65 = 121

이 된다.

만약 어떤 자연수

n

에 대해 라이크렐 함수를 반복적으로 적용했을 때 (

F_b(n), F_b(F_b(n)), ...

) 결코 회문이 되지 않는다면, 그 수

n

을 '''라이크렐 수'''라고 부른다.^[3] 일부 정의에서는

F_{b}^{i + 1}(n) = 2 F_{b}^{i}(n)

을 만족시키는 자연수

i

가 존재하지 않는 경우

n

을 라이크렐 수로 정의하기도 한다.^[1]^[2] 여기서

F^i

는 함수

F

를

i

번 반복 적용한 것을 의미한다.

3. 10진법에서의 라이크렐 수

십진법에서 어떤 수와 그 수를 뒤집은 수를 더하는 과정을 반복하여 회문수를 만드는 것을 '역순 더하기 과정' 또는 '회문 알고리즘'이라고 한다. 예를 들어, 56에 65를 더하면 회문수인 121이 된다 (56 + 65 = 121).

대부분의 수는 이 과정을 몇 번 거치면 회문수가 된다. 10,000 미만의 수 중 약 80%는 4단계 이내, 약 90%는 7단계 이내에 회문수가 되는 것으로 알려져 있다.

57은 2단계 만에 회문수 363이 된다 (57 + 75 = 132, 132 + 231 = 363).
59는 3단계 만에 회문수 1111이 된다 (59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111).
89는 비교적 많은 24단계를 거쳐 8,813,200,023,188이라는 회문수에 도달한다.

하지만 어떤 수들은 이 과정을 아무리 반복해도 회문수가 되지 않는 것으로 추정되며, 이러한 수를 라이크렐 수라고 부른다. 현재 십진법에서는 라이크렐 수의 존재가 수학적으로 증명되지 않았다.^[3]^[18] 따라서 어떤 수가 라이크렐 수라고 확정할 수는 없지만, 오랜 기간 동안 많은 계산을 통해 회문수가 발견되지 않은 수들을 '라이크렐 수 후보'라고 부른다.

가장 작은 라이크렐 수 후보는 196이다. 196이 실제로 라이크렐 수인지는 아직 밝혀지지 않았으며, 이는 '196 문제'로 알려진 미해결 문제이다. 일반적으로 0으로 끝나지 않는 라이크렐 수 후보를 뒤집은 수 역시 라이크렐 수 후보가 된다. 예를 들어 196이 후보이므로 691도 후보가 된다.

라이크렐 수 후보로 여겨지는 다른 수들은 다음과 같다(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'''...

위 목록에서 굵게 표시된 수(196, 879, 1997 등)는 다른 라이크렐 수 후보를 파생시키는 '근원 라이크렐 수' 후보로 여겨진다. 제이슨 도셋(Jason Doucette), 이안 피터스(Ian Peters), 벤자민 데프레스(Benjamin Despres) 등 여러 연구자들이 컴퓨터 계산을 통해 라이크렐 수 후보를 탐색하고 있으며, 특히 벤자민 데프레스는 17자리 미만의 근원 라이크렐 수 후보를 모두 식별하기도 했다.^[4]^[19] 웨이드 반랜딩햄(Wade VanLandingham)은 자릿수별 근원 라이크렐 수 후보의 개수를 집계하여 공개하고 있다.^[5]^[20]

한편, 이진법이나 십육진법과 같이 밑(base)이 2의 거듭제곱인 다른 진법에서는 라이크렐 수가 존재함이 증명되었다.^[33]^[18]

3. 1. 196 문제

196이 라이크렐 수인지, 즉 역순 더하기 과정을 무한히 반복해도 회문수가 되지 않는지 판별하는 문제는 "196 문제"로 불린다.^[22] 196은 회문수를 형성하는 것으로 알려지지 않은 가장 작은 숫자이므로, 가장 작은 라이크렐 수 후보로서 많은 관심을 받아왔다.

1980년대에 196 문제는 마이크로컴퓨터 애호가들 사이에서 주목받기 시작했으며, 짐 버터필드 등이 작성한 검색 프로그램이 여러 컴퓨터 잡지에 소개되기도 했다.^[7]^[8]^[9] 1985년 제임스 킬먼의 프로그램은 28일 이상 실행되어 12,954번의 반복 끝에 5,366자리 숫자에 도달했지만 회문수를 찾지 못했다.^[9]

존 워커는 1987년 8월 12일, Sun 3/260 워크스테이션을 사용하여 196에 대한 본격적인 계산을 시작했다. 그는 숫자를 뒤집어 더하는 과정을 반복하고 각 단계마다 회문수인지 확인하는 C 프로그램을 작성했다. 이 프로그램은 약 3년간 백그라운드에서 낮은 우선순위로 실행되었고, 주기적으로 진행 상황을 저장했다. 1990년 5월 24일, 프로그램은 2,415,836번의 반복을 수행하여 숫자가 100만 자리에 도달하자 중단되었다. 이때까지 회문수는 발견되지 않았다. 워커는 자신의 결과와 마지막 상태를 인터넷에 공개하며 다른 연구자들에게 계산을 이어갈 것을 제안했다.

워커의 작업 이후 여러 연구자들이 196 문제에 도전했다.

1995년, 팀 어빈(Tim Irvin)과 래리 심킨스(Larry Simkins)는 다중 처리 컴퓨터를 사용하여 3개월 만에 200만 자리까지 계산했지만 회문수를 찾지 못했다.
제이슨 도셋(Jason Doucette)은 2000년 5월에 1,250만 자리까지 계산을 진행했다.
웨이드 반랜딩햄(Wade VanLandingham)은 도셋의 프로그램을 사용하여 1,300만 자리를 넘어서, 2006년 5월 1일에는 3억 자리까지 도달하는 기록을 세웠다.
2011년, 로맹 돌보(Romain Dolbeau)는 분산 컴퓨팅^[10]을 활용하여 413,930,770자리까지 계산했으며,^[36] 2015년 2월에는 계산 결과가 10억 자리를 넘어섰다.^[11]^[27]

이러한 대규모 계산 시도에도 불구하고, 현재까지 196에 대한 역순 더하기 과정에서 회문수는 발견되지 않았다.

3. 2. 스레드, 시드 수, 친족 수

'''스레드'''(thread)는 제이슨 도셋(Jason Doucette)이 만든 용어로, 역순으로 더하는 과정을 반복했을 때 회문이 될 수도 있고 그렇지 않을 수도 있는 수열을 의미한다. 어떤 주어진 '''시드 수'''(seed number)와 관련된 '''친족 수'''(kin number)는 같은 스레드로 수렴하게 된다. 스레드는 원래의 시드 수나 친족 수를 포함하지 않으며, 수렴한 뒤 두 수 모두에 공통적으로 나타나는 숫자들만 포함한다.

'''시드 수'''(seed number)는 라이크렐 수의 부분 집합으로, 회문수를 만들어내지 않는 각 스레드에서 가장 작은 수를 가리킨다. 시드 수 자체가 회문수인 경우도 있을 수 있다.

'''친족 수'''(kin number) 역시 라이크렐 수의 부분 집합이며, 시드 수를 제외한 스레드 내의 모든 수를 포함한다. 또는, 단 한 번의 역순 덧셈 반복 후에 특정 스레드로 수렴하는 모든 수를 친족 수라고 할 수 있다. 이 용어는 1997년 야마시타 코지(Koji Yamashita)가 처음 사용했다.

4. 다른 진법에서의 라이크렐 수

10진법 외에 다른 진법에서도 라이크렐 수가 존재하는지에 대한 연구가 이루어지고 있다. 특히 2진법, 4진법, 8진법, 16진법 등 2의 거듭제곱을 밑으로 하는 진법에서는 라이크렐 수가 존재함이 수학적으로 증명되었다.^[13]^[14]^[15] 또한, 3진법, 5진법, 6진법, 7진법, 9진법 등 여러 다른 진법에서도 라이크렐 수이거나 라이크렐 수로 추정되는 수들이 발견되었다. 각 진법에서 가장 작은 라이크렐 수 또는 그 후보에 대한 자세한 목록은 아래 하위 섹션에서 확인할 수 있다.

4. 1. 각 진법에서의 가장 작은 라이크렐 수 (또는 후보)

이진법에서 10110 (10진법으로 22)은 라이크렐 수로 증명되었다. 이 수를 덧셈 후 뒤집기 과정을 반복하면 4단계 후 10110100, 8단계 후 1011101000, 12단계 후 101111010000이 된다. 일반적으로 4''n''단계 후에는 맨 앞에 '10', 그 뒤로 ''n''+1개의 '1', '01', 그리고 마지막으로 ''n''+1개의 '0'이 오는 형태가 되며, 이 수들은 회문이 될 수 없다.

라이크렐 수는 11진법, 17진법, 20진법, 26진법 및 2의 모든 거듭제곱 진법(2진법, 4진법, 8진법, 16진법, 32진법 등)에서 존재함이 증명되었다.^[13]^[14]^[15]

어떤 진법 ''b''에도 ''b''보다 작은 라이크렐 수는 존재하지 않는다. 이는 ''b''진법에서 한 자릿수는 덧셈 후 뒤집는 과정을 많아야 두 번 반복하면 회문이 되기 때문이다.

각 진법에서 라이크렐 수일 가능성이 있는 가장 작은 수는 다음과 같다.

b	b진법의 최소 라이크렐 수 또는 그 후보 (괄호 안은 10진수 값)
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)

5. 음의 정수로의 확장

라이크렐 수는 각 정수를 나타내기 위해 부호-숫자 표현을 사용하여 음의 정수로 확장될 수 있다.

참조

_[1] 웹사이트 Reply to ''Status of the 196 conjecture?'' https://mathoverflow[...] 2012-12-26
_[2] 웹사이트 FAQ https://web.archive.[...]
_[3] 웹사이트 Digit Reversal Sums Leading to Palindromes http://www.mathpages[...]
_[4] 웹사이트 Lychrel Records https://web.archive.[...] 2011-08-29
_[5] 웹사이트 Identified Seeds https://web.archive.[...] 2011-08-29
_[6] 웹사이트 On Non-Brute Force Methods http://home.cfl.rr.c[...]
_[7] 간행물 Bits and Pieces https://archive.org/[...] Transactor Publishing 2014-12-26
_[8] 간행물 Commodares: Programming Challenges https://archive.org/[...] Ion International 1984-10
_[9] 간행물 Commodares: Programming Challenges https://archive.org/[...] Ion International 1985-06
_[10] conference The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest http://www.isc-event[...] 2014-06-23
_[11] 웹사이트 The p196_mpi page http://www.dolbeau.n[...]
_[12] 웹사이트 Lychrel Records https://web.archive.[...] 2016-09-02
_[13] 문서 See comment section in {{OEIS2C|id=A060382}}
_[14] 웹사이트 Digit Reversal Sums Leading to Palindromes http://www.mathpages[...]
_[15] 웹사이트 Letter from David Seal https://web.archive.[...] 2017-03-08
_[16] 웹사이트 Reply to ''Status of the 196 conjecture?'' https://mathoverflow[...] 2012-12-26
_[17] 웹사이트 FAQ https://www.p196.org[...]
_[18] 웹사이트 Digit Reversal Sums Leading to Palindromes https://www.mathpage[...]
_[19] 웹사이트 Lychrel Records https://web.archive.[...] 2011-08-29
_[20] 웹사이트 Identified Seeds https://web.archive.[...] 2011-08-29
_[21] 웹사이트 On Non-Brute Force Methods http://home.cfl.rr.c[...]
_[22] 웹사이트 回文数と196 http://yutaka-nishiy[...]
_[23] 간행물 Bits and Pieces https://archive.org/[...] Transactor Publishing
_[24] 간행물 Commodares: Programming Challenges https://archive.org/[...] Ion International 1984-10
_[25] 간행물 Commodares: Programming Challenges https://archive.org/[...] Ion International 1985-06
_[26] conference The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest http://www.isc-event[...] 2014-06-23
_[27] 웹사이트 The p196_mpi page http://www.dolbeau.n[...]
_[28] 웹사이트 Lychrel Records http://web.archive.b[...] 2016-09-02
_[29] 문서 See comment section in {{OEIS2C|id=A060382}}
_[30] 웹사이트 Letter from David Seal https://web.archive.[...] 2017-03-08
_[31] 웹인용 Reply to ''Status of the 196 conjecture?'' https://mathoverflow[...] 2012-12-26
_[32] 웹인용 FAQ https://www.p196.org[...]
_[33] 웹인용 Digit Reversal Sums Leading to Palindromes http://www.mathpages[...]
_[34] 웹인용 Lychrel Records http://www.p196.org/[...] 2011-08-29
_[35] 웹인용 Identified Seeds http://www.p196.org/[...] 2011-08-29
_[36] 웹인용 The p196_mpi page https://web.archive.[...] 2020-07-22
_[37] 웹인용 Lychrel Records http://web.archive.b[...] 2016-09-02
_[38] 웹인용 Digit Reversal Sums Leading to Palindromes http://www.mathpages[...]
_[39] 웹인용 Letter from David Seal https://web.archive.[...] 2017-03-08

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com