1. 개요
196 Palindrome Quest, 196 Palindrome Problem, 196 회문 문제, 196 회문 알고리즘1984년 4월 Scientific American의 "Computer Recreations" 칼럼에 나온 알고리즘이다.
2. 배경
먼저 대칭수라는 것은 12321과 같이 앞에서부터 읽거나 뒤에서부터 읽어도 같은 수를 말한다.이에 관련하여 어떤 문제가 하나 존재하는 데 아래와 같다.
1. 먼저 아무 자연수나 하나 정한다.
2. 이 수를 뒤집어 뒤집기 전의 숫자와 더한다.
예) 숫자를 125로 했다면 125 + 521 → 646
3. 더한 수가 대칭수가 된다면 종료하고, 그렇지 않다면 대칭수가 될 때까지 2번을 반복한다.
알고리즘은 위와 같다. 무수히 많은 수가 이 방법을 반복하면 언젠가는 대칭수가 나오는 것이 확인되었다. 하지만, 모든 수가 그러한지는 증명되지 않았다. 예를 들어 196으로 시작하여 반복할 경우, 대칭수가 나오는 지에 대해서는 증명도 반증도 되지 않았다. 컴퓨터를 통해 어마어마하게 큰 수가 될때까지 시행하고 있음에도 확인되지 않았다. 196이외에도 여러 수가 있지만, 가장 작은 수가 196이기 때문에 196 Palindrome Quest라고 불린다.2. 이 수를 뒤집어 뒤집기 전의 숫자와 더한다.
예) 숫자를 125로 했다면 125 + 521 → 646
3. 더한 수가 대칭수가 된다면 종료하고, 그렇지 않다면 대칭수가 될 때까지 2번을 반복한다.
3. 역사
| 89 → 187 → 968 → 1837 → 9218 → 17347 → 91718 → 173437 → 907808 → 1716517 → 8872688 → 17735476 → 85189247 → 159487405 → 664272356 → 1317544822 → 3602001953 → 7193004016 → 13297007933 → 47267087164 → 93445163438 → 176881317877 → 955594506548 → 1801200002107 → 8813200023188 |
89(또는 98)로 시작할 경우 24단계 만에 8813200023188 이 되면서 대칭수가 되고 끝이 난다.
밑에 나오는 자릿수란 컴퓨터로 알고리즘을 실행했을 때 모든 단계를 거쳐 나온 숫자의 자릿수를 의미한다. 예를 들어 123으로 알고리즘을 실행했다면 123 + 321 = 444. 그렇다면 자리수는 총 123321444. 9자리가 되는 것이다. 위의 89로 시작화는 경우는 199자리 이다.
당시 년도에 발견된 가장 큰 자릿수는 아래와 같다.
1987 ~ 1990년 : John Walker : 백만 자리
1995년 : Tim Irvin : 2백만 자리
2001년 : Jason Doucette : 천 3백만 자리
현재 : Wade Vanlandingham : 7천만 자리.
지금까지 발견된 수 중에서 자릿수(위에서 말한 자릿수가 아니라 일반적인 수의 자릿수)가 가장 큰 회문수는 1,186,060,307,891,929,990를 시작으로 261단계 돌렸을 때의 결과값인 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 이다.
이 196 Palindrome Quest는 지금까지도 컴퓨터 학자들이 끝없이 계산하고 있다. 만약 언젠가 대칭수가 나온다면 196은 라이크렐 수가 아닌 것으로 판명되고 깔끔하게 문제가 해결된다. 문제는 만약 196이 라이크렐 수가 맞다면 이러한 단순 계산으로는 아무런 사실도 알아내지 못한다는 것이다. 자연수는 무한 개 있으니 이런 방식으로는 맞다는 증명을 하지 못한다. 참고로, 컴퓨터를 이용해서 196을 시작으로 10억 자리가 넘을때까지 반복했지만, 대칭수가 등장하지 않았다.