대칭수(palindromic number)와 $196$

written by jjycjn   2018. 4. 29. 10:53
대칭수(panlindromic number)란, 주어진 숫자를 순서대로 읽은 것과 거꾸로 읽은 것이 일치하는 수를 말한다. 예를 들어 $11$, $252$, $3773$과 같은 수들은 모두 대칭수이다. 숫자를 아무거나 선택하라. 대칭수와 관련해서 1984년 4월 컴퓨터 학자 그루엔버거(F. Gruenberger)는 다음과 같은 알고리즘을 제시하였다.
  1. 임의의 양의 정수를 택한다.
  2. 그 수를 거꾸로 뒤집어 원래의 수와 합한다.
  3. 두 수를 더한 결과가 대칭수가 아니라면, 2번 과정을 다시 되풀이하고, 대칭수라면 알고리즘을 종료한다.
위 알고리즘을 임의의 두자리 양의 정수에 대해서 적용해 보면, 전부 결국에는 대칭수가 됨을 어렵지 않게 확인할 수 있다. 몇 개의 두자리 양의 정수에 대해서 예를 들어 보면 다음과 같다.
\[ \begin{array}{r} \phantom{1} \\ \phantom{1} \\ \text{step 1:} \\ \phantom{1} \\ \phantom{1} \\ \phantom{1} \\ \phantom{1} \end{array} \quad \begin{array}{r} 23 \\ + \; 32 \\ \hline \textcolor{myblue}{55} \\ \phantom{1} \\ \phantom{1} \\ \phantom{1} \\ \phantom{1} \end{array} \qquad \begin{array}{r} \phantom{1} \\ \phantom{1} \\ \text{step 1:} \\ \phantom{1} \\ \text{step 2:} \\ \phantom{1} \\ \phantom{1} \end{array} \quad \begin{array}{r} 37 \\ + \; 73 \\ \hline 110 \\ + \; 011 \\ \hline \textcolor{myblue}{121} \\ \phantom{1} \\ \phantom{1} \end{array} \qquad \begin{array}{r} \phantom{1} \\ \phantom{1} \\ \text{step 1:} \\ \phantom{1} \\ \text{step 2:} \\ \phantom{1} \\ \text{step 3:} \end{array} \quad \begin{array}{r} 86 \\ + \; 68 \\ \hline 154 \\ + \; 451 \\ \hline 605 \\ + \; 506 \\ \hline \textcolor{myblue}{1,111} \end{array} \]
이 알고리즘에서 $89$는 굉장히 특별한 수인데, 다른 모든 두자리 수들은 모두 많아야 여섯 단계 안에 알고리즘이 종료가 되는데 반해, $89$는 총 $24$ 단계를 거쳐야만 최종적으로 대칭수가 된다.[note]http://jasondoucette.com/worldrecords.html[/note]
\[ \begin{array}{r} \phantom{1} \\ \phantom{1} \\ \text{step 1:} \\ \phantom{1} \\ \text{step 2:} \\ \phantom{1} \\ \text{step 3:} \\ \phantom{1} \\ \text{step 4:} \\ \phantom{1} \\ \text{step 5:} \\ \phantom{1} \\ \text{step 6:} \\ \phantom{1} \\ \text{step 7:} \\ \phantom{1} \\ \text{step 8:} \\ \phantom{1} \\ \text{step 9:} \\ \phantom{1} \\ \text{step 10:} \\ \phantom{1} \\ \text{step 11:} \\ \phantom{1} \\ \text{step 12:} \\ \phantom{1} \\ \text{step 13:} \\ \phantom{1} \\ \text{step 14:} \\ \phantom{1} \\ \text{step 15:} \\ \phantom{1} \\ \text{step 16:} \\ \phantom{1} \\ \text{step 17:} \\ \phantom{1} \\ \text{step 18:} \\ \phantom{1} \\ \text{step 19:} \\ \phantom{1} \\ \text{step 20:} \\ \phantom{1} \\ \text{step 21:} \\ \phantom{1} \\ \text{step 22:} \\ \phantom{1} \\ \text{step 23:} \\ \phantom{1} \\ \text{step 24:} \end{array} \quad \begin{array}{r} 89 \\ + \; 98 \\ \hline 187 \\ + \; 781 \\ \hline 968 \\ + \; 869 \\ \hline 1,837 \\ + \; 7,381 \\ \hline 9,218 \\ + \; 8,129 \\ \hline 17,347 \\ + \; 74,371 \\ \hline 91,718 \\ + \; 81,719 \\ \hline 173,437 \\ + \; 734,371 \\ \hline 907,808 \\ + \; 808,709 \\ \hline 1,716,517 \\ + \; 7,156,171 \\ \hline 8,872,688 \\ + \; 8,862,788 \\ \hline 17,735,476 \\ + \; 67,453,771 \\ \hline 85,189,247 \\ + \; 74,298,158 \\ \hline 159,487,405 \\ + \; 504,784,951 \\ \hline 664,272,356 \\ + \; 653,272,466 \\ \hline 1,317,544,822 \\ + \; 2,284,457,131 \\ \hline 3,602,001,953 \\ + \; 3,591,002,063 \\ \hline 7,193,004,016 \\ + \; 6,104,003,917 \\ \hline 13,297,007,933 \\ + \; 33,970,079,231 \\ \hline 47,267,087,164 \\ + \; 46,178,076,274 \\ \hline 93,445,163,438 \\ + \; 83,436,154,439 \\ \hline 176,881,317,877 \\ + \; 778,713,188,671 \\ \hline 955,594,506,548 \\ + \; 845,605,495,559 \\ \hline 1,801,200,002,107 \\ + \; 7,012,000,021,081 \\ \hline \textcolor{myblue}{8,813,200,023,188} \end{array} \]

$ $

라이크렐 수(Lychrel number)

어떤 양의 정수를 택하더라도 위 알고리즘을 반복해서 적용하면 결국은 대칭수가 될까? 위 알고리즘을 무한번 반복하더라도 절대로 대칭수가 되지 않는 양의 정수를 라이크렐 수(Lychrel number)이라 하는데, 위 질문은 결국 라이크렐 수가 존재하는지의 여부를 묻는 것과 같다. 현재까지 라이크렐 수가 존재하는지의 여부는 증명되지 않았는데, 라이크렐 수의 후보로 여겨지는 가장 작은 수는 $196$이다. 현재까지 알려진 바에 의하면, $196$의 경우 알고리즘을 $1,000,000,000$번을 반복하여도 대칭수가 되지 않으며, 알고리즘을 통해 산출된 마지막 수는 모두 $413,930,770$자리나 되는 수라고 한다.[note]http://www.p196.org/news.html[/note] $196$ 이외에 라이크렐 수일 것이라 여겨지는 수들의 목록은 다음과 같다.[note]이 수열은 OEIS에 수열 번호 A023108로 등록되어 있다.[/note]
\[ \begin{align*} & 196,\, 295,\, 394,\, 493,\, 592,\, 689,\, 691,\, 788,\, 790,\, 879,\, 887, \\[5px] & 978,\, 986,\, 1495,\, 1497,\, 1585,\, 1587,\, 1675,\, 1677,\, 1765,\, \ldots \end{align*} \]

$ $

가장 많은 알고리즘 반복수를 요구하는 수

그렇다면 결국 대칭수가 되는 수 중에서, 가장 많은 알고리즘 반복수를 갖는 수는 어떤 수일까? 다음 $19$ 자리수
\[ 1,186,060,307,891,929,990 \]
는 2005년 말에 총 $261$번의 알고리즘 반복을 통해서 결국 대칭수가 됨이 밝혀졌다. 이 수는 현재까지 알려진 가장 많은 알고리즘 반복수를 요구하는 수이며, 이 수를 $261$번의 알고리즘 반복 적용을 통해 생성한 대칭수는 모두 $119$ 자리수를 갖는다.
\[ \begin{align*} 44, & 562,665,878,976,437,622,437,848,976,653,870,388,884, \\[5px] & 783,662,598,425,855,963,436,955,852,489,526,638,748, \\[5px] & 888,307,835,667,984,873,422,673,467,987,856,626,544 \end{align*} \]
$2005$년의 발견 이후, 2017년 초 러시아의 한 학생은 $261$번의 알고리즘 반복수를 갖는 $126$개의 양의 정수 수열을 그의 홈페이지에 제시하였다.[note]이 수열은 OEIS에 수열 번호 A281506로 등록되어 있다.[/note] 이 수열은 위에서 언급한 $1,186,060,307,891,929,990$에서 시작하여 $1,999,291,987,030,606,810$에서 끝난다. 또한 $261$번보다 더 많은 알고리즘 반복수를 갖는 양의 정수는 현재까지 알려져 있지 않다.


  ::  
  • 공유하기  ::