d라이브러리

숫자 놀이 한번 해볼까? 숫자를 가지고 장난치는 건 언제나 재밌단 말이지~. 음…. 그런데 이 문제는 쉽지 않아 보이는걸. 도전하고 싶은 마음이 불타올라~!

오일러 프로젝트 55번 문제는 앞뒤가 똑같은 대칭수와 관련이 있다. 예를 들어 121이라는 수를 보자. 숫자 배열이 앞뒤로 대칭을 이룬다는 것을 한눈에 알아볼 수 있다. 이처럼 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 숫자 배열이 같은 수를 ‘대칭수(팰린드롬 수)’라고 부른다.
121의 경우 47과 47의 숫자 배열을 뒤집은 수인 74를 더해 만들어진다. 물론 모든 수가 한 단계 만에 쉽게 대칭수를 만들지는 못한다. 예를 들어 349의 경우 대칭수를 만들기까지 아래와 같은 3단계를 거쳐야 한다.

그런데 196은 이런 과정을 아무리 반복해도 대칭수가 되지 않는 것으로 현재까지 알려져 있다. 이런 수를 ‘라이크렐 수(Lychrel number)’라고 부르며, 196 외에도 여러 개의 라이크렐 수 후보들이 존재한다. 196을 비롯한 라이크렐 수 후보들이 라이크렐 수가 맞는지는 아직 완벽히 증명되지는 않은 상황이다.
라이크렐 수가 있다고 가정하고 분석한 결과에 따르면 1만 이하의 수에 대해 대칭수를 만드는 과정을 반복했을 때 50번을 기점으로 그때까지 대칭수가 나오지 않으면 라이크렐 수 후보가 된다. 1만을 넘는 수 중에는 10677이 53번의 반복으로 4668731596684224866951378664라는 28자리의 대칭수가 된다.
그러면 1만 이하에는 몇 개의 라이크렐 수 후보가 존재할까? 오일러 프로젝트 55번은 그 수들을 찾는 문제다.

라이크렐 수가 아직 증명되지 않은 이유
대칭수를 만드는 방법은 쉽고 단순하지만 대칭수가 나오기까지 계산을 계속 반복해야 한다는 단점이 있다. 196이라는 짧은 수가 대칭수인지 라이크렐 수인지 아직도 분명히 밝혀지지 않은 것도 그 이유 때문이다.
컴퓨터가 발전하면서 많은 학자가 컴퓨터 계산으로 196이 대칭수가 되는지를 알아봤다. 존 워커라는 학자는 1987년부터 1990년까지 100만 자리가 될 때까지 계산했지만 대칭수가 나오지 않았다. 1995년 팀 어빈은 200만 자리까지 계산했지만 결과는 마찬가지였다. 2001년 제이슨 도세트는 1300만 자리까지, 반 랜딩햄은 7000만 자리까지 계산했지만 196은 대칭수가 되지 않았다. 현재 학자들은 196을 대칭수가 되지 않는 최초의 수이자 가장 작은 수로 추정하고 있다. 이번 문제에서는 196을 포함해 대칭수를 찾는 계산을 50번 미만 반복했을 때 대칭수가 나오지 않는 수들을 모두 라이크렐 수로 가정하고 문제를 풀기로 한다. 이제 시작해 보자! 

※오일러 프로젝트란?
2001년 수학과 프로그래밍 실력을 모두 키울 수 있도록 만든 수학 문제 웹사이트로, 수학 문제를 프로그래밍으로 해결하는 게 목적이다. 현재 600개 이상의 문제가 올라와 있으며, 2주에 1번씩 새로운 문제가 추가된다. 오일러 프로젝트 문제를 한국어로 번역한 사이트도 있으니 기사를 읽고 오일러 프로젝트에 참여해 보자.