세 대칭수(palindromic number)의 합

      Comments Off on 세 대칭수(palindromic number)의 합

다음의 계산을 보자.

\[ \begin{matrix} & 2 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 2 \\ + & & 9 & 9 & 8 & 8 & 1 & 1 & 8 & 8 & 9 & 9 \\ + & & & 4 & 2 & 6 & 7 & 9 & 7 & 6 & 2 & 4 \\ \hline & 3 & 1 & 4 & 1 & 5 & 9 & 2 & 6 & 5 & 3 & 5 \end{matrix} \]

위 계산에서 볼 수 있듯이 원주율 $\pi$의 소숫점 아래 열번째 자리까지 나열한 수를 세개의 대칭수(palindromic number)의 합으로 표현한 것을 알 수 있다. 여기서 대칭수란 앞에서부터 순서대로 읽은 수와 뒤에서부터 거꾸로 읽은 수가 일치하는 수를 말한다. 한편, 자연상수 $e$의 경우에서도 마찬가지 관찰을 할 수 있는데, 자연상수의 소숫점 열번째 자리까지 나열한 수 또한 아래와 같이 세 대칭수의 합으로 나타낼 수 있다. \[ \begin{matrix} & 2 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 2 \\ + & & 6 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 6 \\ + & & & 6 & 3 & 7 & 3 & 6 & 3 & 7 & 3 & 6 \\ \hline & 2 & 7 & 1 & 8 & 2 & 8 & 1 & 8 & 2 & 8 & 4 \end{matrix} \] 잘 알려져 있는 두 상수 원주율과 자연상수에 또 다른 새로운 수학적 사실이 숨어 있는 것일까? 논문 [1]에 의하면, 사실 임의의 양의 정수는 언제나 세 개 이하의 대칭수의 합으로 표현이 가능하다!

$ $

정리.

정수 $g \geq 5$에 대하여, 임의의 양의 $g$진수는 언제나 세 개 이하의 $g$진 대칭수의 합으로 표현할 수 있다.

$ $

특히 위 정리에서 $g=10$인 경우, 임의의 양의 정수를 언제나 세 개 이하의 대칭수의 합으로 표현할 수 있음을 알 수 있다. 또한 예를 들어 $5$진법에서도 \[ \begin{matrix} & 4 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 4 \; {}_{(5)} \\ + & & 2 & 2 & 2 & 4 & 4 & 4 & 2 & 2 & 2 \; {}_{(5)} \\ + & & & 4 & 2 & 4 & 3 & 3 & 4 & 2 & 4 \; {}_{(5)} \\ \hline & 4 & 3 & 2 & 1 & 0 & 4 & 3 & 2 & 1 & 0 \; {}_{(5)} \end{matrix} \] 와 같이 주어진 $5$진수를 세 개의 $5$진 대칭수의 합으로 표현할 수 있다.

$ $

위 정리의 증명이 특별한 이유 중 하나는, 여타 다른 존재성 정리의 증명과 다르게 구성적 증명적(constructive proof)이라는 점이다. 위 정리의 증명을 보면, 양의 정수의 집합을 몇 가지의 케이스로 나누고, 각각의 경우마다 세 개의 대칭수를 구하는 알고리즘을 직접 제시하고 있다. 이 알고리즘을 이용하여 실제로 세 대칭수를 구해주는 사이트는 아래 링크를 클릭하여 들어갈 수 있다.

$ $

Sum of Three Palindromes

$ $

위 정리가 소개되어 있는 논문에는 $g = 2,\,3,\,4$인 경우는 다루고 있지 않다. 다만 $g=2$인 경우 위 정리가 성립하지 않을 수 있음을 쉽게 짐작이 가능하다. 이진 대칭수의 마지막 자리는 반드시 $1$이어야 하기 때문에, 세 개의 이진 대칭수의 합의 마지막 자리 또한 $1$이 된다. 즉, 마지막 자리가 $0$인 이진수는 (위 정리가 $g=2$에서도 참이라고 가정한다면) 두 개의 이진 대칭수의 합으로 표현해야만 한다. 하지만 $1001010_{(2)}$는 두개의 이진 대칭수의 합으로 표현이 불가능하다. (이 수는 두 개의 이진 대칭수의 합으로 표현이 불가능한 수 중 가장 작은 수이다.)

$ $

논문 [2]에서는 $g=2,\,3,\,4$인 경우에 대한 정리가 포함되어 있다.

$ $

정리.

정수 $g =3,\,4$에 대하여, 임의의 양의 $g$진수는 언제나 세 개 이하의 $g$진 대칭수의 합으로 표현할 수 있다. 또한 $g = 2$인 경우, 임의의 양의 이진수는 언제나 네 개 이하의 이진 대칭수의 합으로 표현 가능하다.

$ $

따라서 정리 1과 정리 2를 통해, $g=2$인 경우를 제외한 모든 $g$진수는 세 개 이하의 $g$진 대칭수의 합으로 표현이 가능함을 알 수 있다.

$ $

참고 문헌
  1. Javier Cilleruelo, Florian Luca, Lewis Baxter, "Every positive integer is a sum of three palindromes", arXiv:1602.06208 [math.NT]
  2. Aayush Rajasekaran, Jeffrey Shallit, Tim Smith, "Sums of Palindromes: an Approach via Automata", arXiv:1706.10206 [cs.FL]