리크렐 수

수학의 미해결 문제:

베이스-10 Lychrel 수치가 존재하나?

리크렐 번호는 숫자를 번복하고 그 결과 숫자를 추가하는 반복적인 과정을 통해 구분을 형성할 수 없는 자연수다. 이 과정은 때때로 196-알고리즘이라고 불리는데, 그 과정과 관련된 가장 유명한 숫자의 이름을 따왔다. 베이스 10에서는 리크렐 수치가 아직 존재한다는 것이 증명되지 않았지만, 196을 포함한 많은 수가 휴리스틱스적이고^[1] 통계적인 근거로 의심받고 있다. '리크렐'이라는 이름은 웨이드 밴 랜딩햄이 여자친구의 이름인 '체릴'의 거친 애너그램으로 지어졌다.^[2]

역 및 추가 프로세스

역추적 과정은 숫자와 숫자의 순서를 거꾸로 하여 형성된 숫자의 합을 산출한다. 예를 들어, 56 + 65 = 121. 또 다른 예로 125 + 521 = 646을 들 수 있다.

어떤 숫자들은 반전과 덧셈을 반복한 후에 빨리 팔린드로 되어, 따라서 리크렐 숫자가 아니다. 모든 한 자릿수와 두 자릿수는 결국 반전과 덧셈을 반복한 끝에 팔린드롬이 된다.

10,000 이하 모든 숫자의 약 80%는 4단계 이하로, 약 90%는 7단계 이하로 결정된다. 다음은 비 Lychrel 숫자의 몇 가지 예:

56은 한 번 반복하면 팔린드로믹해진다: 56+65 = 121.
57은 두 번 반복하면 팔린드로믹해진다: 57+75 = 132, 132+231 = 363.
59+95 = 154, 154+451 = 605, 605+506 = 1111의 세 번을 반복한 후에 회문이 된다.
89는 특이하게 큰 24번의 반복을 필요로 한다(팔라인드로 분해되는 것으로 알려진 1만 이하의 숫자들 중 가장 많은 숫자)는 팔라인드롬에 도달한다.
10,1987은 55단계 후 46687315966842246951378664(28자리)에 이른다.
1,186,060,307,891,929,990 takes 261 iterations to reach the 119-digit palindrome 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544, which was a former world record for the Most Delayed Palindromic Number. 2005년 11월 30일 제이슨 더켓의 알고리즘과 프로그램(벤자민 데프레스의 역추적 코드를 사용)에 의해 해결되었다.
2017년 1월 23일, 러시아 학생 안드레이 S. 슈체베토프는 자신의 웹사이트를 통해 119자리 팔린드롬에 도달하기 위해 정확히 261개의 조치를 취하는 첫 번째 126개의 숫자(이전까지 보고되지 않은 125개의 숫자)의 순서를 발견했다고 발표했다. 이 순서는 OEIS에서 A281506으로 발행되었다. 이 순서는 2005년 제이슨 더켓이 발견한 유일한 공식 번호인 1,186,060,307,891,929,990으로 시작되었다. 2017년 5월 12일 이 순서는 총 108864항으로 연장되었으며, 261단계 지연이 있는 최초의 108864 지연 팔레드롬을 포함하였다. 연장된 순서는 그것의 최대이자 마지막 기간인 1,999,291,987,030,606,810으로 끝났다.
2019년 4월 26일, 롭 반 노벨렌은 가장 지연된 팔린드로믹 숫자의 세계 신기록을 계산했다: 1,200억 7,000억 25,339,936,491은 142자리 숫자의 팔린드로메이트에 도달하기 위해 288번 반복한다.
2021년 1월 5일 안톤 스테파노프는 가장 지연된 팔린드로믹 번호 2개를 새로 계산했다: 13968441660506386020과 135684460506503386420은 롭 반 노벨렌 번호와 동일한 142자리 숫자의 팔라인드롬에 도달하기 위해 289번 반복한다.
2021년 12월 14일 드미트리 마슬로프는 가장 지연된 팔린드로믹 번호의 세계 신기록을 계산했다: 100,206,827,388,999,099,095,750은 132자리 팔린드로롬에 도달하는데 293번 반복한다.
OEIS 시퀀스 A326414에는 현재 288단계 지연이 알려진 19353600 항이 포함되어 있다.
A281506의 어떤 숫자도 261단계 팔레드롬의 고차적 구성을 위한 1차적 기반으로서 사용될 수 있다. For example, based on 1,999,291,987,030,606,810 the following number 199929198703060681000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001999291987030606810 also becomes a 238-digit palindrome 4456266587897643762243784897665387038888478366259842585596343695585248952663874888830783566798487342267346798766526544 4456658789764224376489766868486868684784782598825825855963495585895868838868838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838838

회반죽을 형성하지 않은 것으로 알려져 있는 가장 작은 숫자는 196이다. 그것은 가장 작은 Lychrel 번호 후보 이다.

리크렐 숫자의 숫자가 0으로 끝나지 않는 반전에 따른 숫자도 리크렐 숫자다.

프로세스의 공식 정의

$n$ $n$ 을(를) 자연수가 되게 $n$ 하라. 숫자 $b>1$ b > 1 $b>1$ $F_{b}:\mathbb {N} \rightarrow \mathbb {N}$ : $F_{b}:\mathbb {N} \rightarrow \mathbb {N}$ → $F_{b}:\mathbb {N} \rightarrow \mathbb {N}$ ${\$ 에 대한 Lychrel 함수를 정의하여 다음과 $F_{b}:\mathbb {N} \rightarrow \mathbb {N}$ 같이 한다.

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

여기서 $k=\lfloor \log _{b}{n}\rfloor +1$ = $k=\lfloor \log _{b}{n}\rfloor +1$ $k=\lfloor \log _{b}{n}\rfloor +1$ b $k=\lfloor \log _{b}{n}\rfloor +1$ + $k=\lfloor \log _{b}{n}\rfloor +1$ {\ $displaystyle k=\lfloor \log _{b$ }\ $n}\proper$ loor $+1}$ 는 $k=\lfloor \log _{b}{n}\rfloor +1$ $기본$ b ${\displaystyle b$ 및

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

숫자의 각 자릿수 값이다. A number is a Lychrel number if there does not exist a natural number $i$ such that $F_{b}^{i+1}(n)=2F_{b}^{i}(n)$ , where $F^{i}$ is the $i$ -th iteration of $F$

증거를 찾을 수 없음

다른 베이스(이 베이스는 2진수, 16진수 등 2진수)에서는 일정한 숫자가 반전과 덧셈을 반복한 후 결코 구분을 형성하지 않는다는 것을 증명할 수 있지만,^[3] 196과 다른 베이스 10수에 대해서는 그러한 증거가 발견되지 않았다.

196을 비롯한 아직 구분이 나지 않은 숫자들은 리크렐 수라고 추측되지만 베이스 10의 숫자는 아직 리크렐로 증명되지 않았다. Rychrel이 아닌 것으로 증명되지 않은 숫자를 비공식적으로 "Lychrel 후보" 번호라고 부른다. Lychrel 후보 번호(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.

굵은 글씨로 표시된 숫자는 Lychrel 씨 번호로 의심된다(아래 참조). 제이슨 더켓, 이안 피터스, 그리고 벤자민 데브레스의 컴퓨터 프로그램은 다른 라이크렐 후보들을 찾아냈다. 실제로 벤자민 데브레스의 프로그램은 17자리 미만의 리크렐 종자로 의심되는 모든 번호를 확인했다.^[4] Wade Van Landingham의 사이트에는 각 자릿수 길이에 대해 발견된 Lychrel로 의심되는 시드 번호의 총 수가 나열되어 있다.^[5]

존 워커에 의해 원래 배치되었던 흉포한 포스 방식은 반복적인 행동을 이용하도록 개선되었다. 예를 들어, Vaughn Suite는 각 반복의 처음과 마지막 몇 자리만 저장하는 프로그램을 고안하여, 각 반복을 파일에 저장하지 않고도 수백만 번의 반복으로 숫자 패턴을 테스트할 수 있도록 하였다.^[6] 그러나, 지금까지 반전과 추가 반복 과정을 회피하기 위한 알고리즘은 개발되지 않았다.

스레드, 시드 및 킨 번호

제이슨 더켓이 만든 실이라는 용어는 역행과 덧셈 과정을 통해 갈림길로 이어질 수도 있고 아닐 수도 있는 숫자의 순서를 가리킨다. 주어진 씨앗과 관련된 혈연수는 같은 실에 모일 것이다. 실에는 원래 씨앗이나 친족 숫자가 들어 있지 않고, 그들이 수렴한 후에 두 사람에게 공통되는 숫자만 들어 있다.

시드 번호는 라이크렐 숫자의 하위 집합으로, 이는 실을 생산하는 각 비팔라인드롬 중에서 가장 작은 숫자다. 종자 번호는 그 자체일 수도 있다. 앞의 세 가지 예는 위 목록에 굵은 글씨로 나타나 있다.

킨 번호는 리크렐 숫자의 하위 집합으로, 씨앗을 제외한 모든 스레드의 숫자 또는 단일 반복 후에 주어진 스레드에 수렴되는 숫자를 포함한다. 이 용어는 1997년 야마시타 고지(山時田)에 의해 도입되었다.

196 팔레드롬 탐색

196(베이스-10)이 가장 낮은 후보인 리크렐 수이기 때문에 가장 많은 관심을 받았다.

1980년대 196개 흑백문제는 여러 대중 시장 컴퓨터 잡지에 짐 버터필드 등의 검색 프로그램이 등장하면서 마이크로 컴퓨터 취미론자들의 관심을 끌었다.^[7]^[8]^[9] 1985년 제임스 킬먼에 의한 프로그램은 28일 이상 동안 실패하여 12,954개의 패스를 통과했고 5366자리 숫자에 도달했다.^[9]

존 워커는 1987년 8월 12일 Sun 3/260 워크스테이션에서 196 Palindrome Quest를 시작했다. 그는 반전과 덧셈 반복을 수행하고 각 단계 후에 팔목현상을 확인하는 C 프로그램을 작성했다. 프로그램은 우선순위가 낮은 백그라운드로 진행돼 2시간마다 파일 체크포인트를 만들어 시스템이 종료되면 지금까지 도달한 수와 반복 횟수를 기록했다. 셧다운이 끝날 때마다 마지막 체크포인트에서 자동으로 재가동했다. 그것은 거의 3년간 운영되었다가 1990년 5월 24일 (지시에 따라) 다음과 같은 메시지와 함께 종료되었다.

패스 2,415,836에서 정지점에 도달했다.

숫자는 100만자리를 포함한다.

196은 241만5천836번 반복한 후 팔레드롬에 도달하지 않고 100만자리 숫자로 성장했다. 워커는 자신의 연구 결과를 마지막 체크포인트와 함께 인터넷에 공개하고, 지금까지 도달한 번호를 이용해 다른 사람들을 초대해 퀘스트를 재개하도록 했다.

1995년 팀 어빈과 래리 심킨스는 멀티프로세서 컴퓨터를 사용했고 석 달 만에 팔레드롬을 발견하지 못하고 200만 자릿수 기록을 달성했다. 제이슨 더켓은 그 뒤를 이어 2000년 5월에 1,250만자리 숫자에 도달했다. Wade VanLandingham은 Jason Doucette의 프로그램을 사용하여 1,300만 자리수를 기록했는데, 이 기록은 Yes Mag: Canada's Science Magazine for Kids에 발표되었다. 2000년 6월부터 웨이드 반랜딩햄은 다양한 마니아들이 작성한 프로그램을 이용해 국기를 달고 있다. 2006년 5월 1일까지 반랜딩햄은 3억자리(5~7일마다 100만자리 비율)에 도달했다. 분산 처리를 이용해 2011년 로맹 돌보는 10억 번을 반복해 413,930,770자리의 숫자를 만들었고, 2015년 2월 그의 계산은 10억 자리 숫자에 도달했다.^[10]^[11] 회향은 아직 발견되지 않았다.

같은 반복 역반전력 방법을 적용받은 다른 잠재적 리크렐 수치로는 879, 1997, 7059를 들 수 있다. 그들은 구분이 발견되지 않은 채 수백만번 반복되었다.^[12]

기타 베이스

베이스 2에서 10110(십진수 22)은 리크렐 숫자로 증명되었는데, 4단계가 지나면 10110100이 되고, 8단계가 지나면 1011101000이 되고, 12단계가 지나면 101111010000이 되며, 일반적으로 4n단계가 지나면 10단계가 되고, 그 다음이 n+1이 되고, 그 다음이 01이 되고 그 뒤에 01이 된다. 이 숫자는 분명히 흑백일 수 없으며, 순서에 있는 다른 숫자들은 하나도 흑백일 수 없다.

리크렐 수치는 11, 17, 20, 26, 그리고 2의 모든 힘을 가진 기초에 존재하는 것으로 증명되었다.^[13]^[14]^[15]

베이스보다 작은 Lychrel 숫자를 포함하는 베이스는 없다. 사실, 어떤 주어진 b 베이스에서는, 한자리 숫자가 팔레드롬을 형성하는 데 두 번 이상 반복되지 않는다. b > 4의 경우, k < b/2인 경우, k는 base b(따라서 alindrome)에서 한 자릿수인 k + k = 2k를 반복한 후에 alindromic이 된다. k > b/2일 경우, k는 두 번 반복한 후 팔린드로믹이 된다.

Lychrel 번호가 될 수 있는 각 베이스의 최소 숫자는 다음과 같다(OEIS에서 순서 A060382).

b	기준 b에서 가능한 최소 Lychrel 수 base로 표기된 (base 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)
31	TU(929)
32	UV(991)
33	VW(1055)
34	1IV(1799)
35	1JW(1922년)
36	YZ(1259)

음의 정수로 확장

리크렐 숫자는 각 정수를 나타내기 위해 부호화된 숫자 표현을 사용함으로써 음의 정수로 확장될 수 있다.

참고 항목

참조

^ O'Bryant, Kevin (26 December 2012). "Reply to Status of the 196 conjecture?". MathOverflow.
^ "FAQ". Archived from the original on 2006-12-01.
^ Brown, Kevin. "Digit Reversal Sums Leading to Palindromes". MathPages.
^ VanLandingham, Wade. "Lychrel Records". p196.org. Archived from the original on 2016-04-28. Retrieved 2011-08-29.
^ VanLandingham, Wade. "Identified Seeds". p196.org. Archived from the original on 2016-04-28. Retrieved 2011-08-29.
^ "On Non-Brute Force Methods". Archived from the original on 2006-10-15.
^ "Bits and Pieces". The Transactor. Transactor Publishing. 4 (6): 16–23. 1984. Retrieved 26 December 2014.
^ Rupert, Dale (October 1984). "Commodares: Programming Challenges". Ahoy!. Ion International (10): 23, 97–98.
^ ^a ^b Rupert, Dale (June 1985). "Commodares: Programming Challenges". Ahoy!. Ion International (18): 81–84, 114.
^ Swierczewski, Lukasz; Dolbeau, Romain (June 23, 2014). The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest. International Supercomputing Conference. Leipzig, Germany.
^ Dolbeau, Romain. "The p196_mpi page". www.dolbeau.name.
^ "Lychrel Records". Archived from the original on December 5, 2003. Retrieved September 2, 2016.
^ OEIS: A060382의 주석 섹션을 참조하십시오.
^ "Digit Reversal Sums Leading to Palindromes".
^ "Letter from David Seal". Archived from the original on 2013-05-30. Retrieved 2017-03-08.

외부 링크

OEIS 시퀀스 A023108(분명히 ...에 따라 구분이 생기지 않는 양의 정수)
John Walker – 컴퓨팅 3년
Tim Irvin – 약 2개월 간의 컴퓨팅 작업
Jason Doucette – 세계 기록 – 196 Palindrome Quest, 가장 지연된 Palindromic 번호
벤저민 데프레스
196 및 Wade VanLandingham의 기타 Lychrel 번호
Weisstein, Eric W. "196-Algorithm". MathWorld.
MathPages – Palindromes로 이어지는 숫자 반전 합계
넘버필
알려진 모든 지연 팔린드롬 숫자 – Drimtry Maslov, MDPN 프로젝트
지연된 팔라인드 테스트 – Drimtry Maslov, MDPN 프로젝트

[1] O'Bryant, Kevin (26 December 2012). "Reply to Status of the 196 conjecture?". MathOverflow.

[2] "FAQ". Archived from the original on 2006-12-01.

[3] Brown, Kevin. "Digit Reversal Sums Leading to Palindromes". MathPages.

[4] VanLandingham, Wade. "Lychrel Records". p196.org. Archived from the original on 2016-04-28. Retrieved 2011-08-29.

[5] VanLandingham, Wade. "Identified Seeds". p196.org. Archived from the original on 2016-04-28. Retrieved 2011-08-29.

[6] "On Non-Brute Force Methods". Archived from the original on 2006-10-15.

[transactor406-7] "Bits and Pieces". The Transactor. Transactor Publishing. 4 (6): 16–23. 1984. Retrieved 26 December 2014.

[ahoy1984-8] Rupert, Dale (October 1984). "Commodares: Programming Challenges". Ahoy!. Ion International (10): 23, 97–98.

[ahoy1985-9] Rupert, Dale (June 1985). "Commodares: Programming Challenges". Ahoy!. Ion International (18): 81–84, 114.

[10] Swierczewski, Lukasz; Dolbeau, Romain (June 23, 2014). The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest. International Supercomputing Conference. Leipzig, Germany.

[11] Dolbeau, Romain. "The p196_mpi page". www.dolbeau.name.

[12] "Lychrel Records". Archived from the original on December 5, 2003. Retrieved September 2, 2016.

[13] OEIS: A060382의 주석 섹션을 참조하십시오.

[14] "Digit Reversal Sums Leading to Palindromes".

[15] "Letter from David Seal". Archived from the original on 2013-05-30. Retrieved 2017-03-08.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search