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번을 반복한다.
알고리즘은 위와 같다. 이 방법을 반복하면 언젠가는 대칭수가 나오는 듯하다.2. 이 수를 뒤집어 뒤집기 전의 숫자와 더한다.
예) 숫자를 125로 했다면 125 + 521 → 646
3. 더한 수가 대칭수가 되지 않았다면 대칭수가 될 때까지 2번을 반복한다.
그런데 이 알고리즘을 컴퓨터를 통해 몇 년 전부터 계속 반복해서 시행하고 있음에도 아직까지도 대칭수가 되지 않는 수들이 존재한다. 이런 수 중에서 가장 작은 수가 196이기 때문에 196 Palindrome Quest라고 불린다.
3. 역사
밑에 나오는 자릿수란 컴퓨터로 알고리즘을 실행했을 때 모든 단계를 거쳐 나온 숫자의 자릿수를 의미한다. 예를 들어 123으로 알고리즘을 실행했다면 123 + 321 = 444. 그렇다면 자리수는 총 123321444. 9자리가 되는 것이다.당시 년도에 발견된 가장 큰 자릿수
1987 ~ 1990년 : John Walker : 백만 자리
1995년 : Tim Irvin : 2백만 자리
2001년 : Jason Doucette : 천 3백만 자리
현재 : Wade Vanlandingham : 7천만 자리.
4. 기타
이 196 Palindrome Quest는 지금까지도 컴퓨터 학자들이 끝없이 계산하고 있다. 만약 언젠가 대칭수가 나온다면 196은 라이크렐 수가 아닌 것으로 판명되고 깔끔하게 문제가 해결된다. 문제는 만약 196이 라이크렐 수가 맞다면 이러한 단순 계산으로는 아무런 사실도 알아내지 못한다는 것이다. 자연수는 무한 개 있으니 이런 방식으로는 맞다는 증명을 하지 못한다.지금까지 발견된 수 중에서 자릿수(위에서 말한 자릿수가 아니라 일반적인 수의 자릿수)가 가장 큰 회문수는 1,186,060,307,891,929,990을 알고리즘으로 돌렸을 때의 수인
44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544이다.