[해답] 숫자의 지속성 (Persistence of Numbers)

※ 이 글은 아래 문제에 대한 해답을 다루고 있습니다.

[문제] 숫자의 지속성 (Persistence of Numbers)

문제의 정답

지속성 5를 갖는 가장 작은 수는 679로서, 679 → 378 → 168 → 48 → 32 → 6 의 다섯 단계를 거쳐 한자리 수가 된다. 또한 지속성 5를 갖는 두번째로 작은 수는 688로서, 688 → 384 → 96 → 54 → 20 → 0 의 다섯 단계를 거쳐 한자리 수가 된다. 1부터 11까지의 자연수 k에 대하여, 지속성 k를 갖는 최소의 자연수들을 표로 정리하면 아래와 같다.

지속성	자연수
1	10
2	25
3	39
4	77
5	679
6	6,788
7	68,889
8	2,677,889
9	26,888,999
10	3,778,888,999
11	277,777,788,888,899

지속성 12를 갖는 최소의 자연수는 알려져 있지 않다. Wikipedia에 따르면, $10^{50}$ 이하의 모든 자연수는 지속성이 11 이하라고 한다.

(덧셈에 대한) 지속성에 대하여

(곱셈에 대한) 지속성과는 달리 (덧셈에 대한) 지속성은 상한이 존재하지 않는다. 자세한 내용과 증명은 다음과 같다.

정리. (덧셈에 대한) 지속성 $k$를 갖는 자연수 $n$이 존재하면, 지속성 $k+1$를 갖는 자연수가 반드시 존재한다.

증명. 만약 자연수 $n > 1$이 지속성 $k$를 갖는다고 가정하자. 이제 다음과 같이 자연수 $m$을 정의하자.

\[ m := \underbrace{111 \cdots 11}_{n \text{ 번 반복}}. \]

그러면, $m$은 (각 자릿수를 더하는) 한 단계를 거치면 $n$으로 변화하고, $n$은 $k$ 단계를 거쳐서 한자리 수로 변화하므로, $m$은 자명하게 지속성 $k+1$을 갖게 된다. ■

위의 정리에 대한 따름 정리로써 다음의 사실도 확인할 수 있다. (아래 수열의 일반항을 간단히 표현할 수 있을까?)

따름정리. 아래와 같이 정의된 수열

\[ n_1 = 2, \qquad n_{k+1} = \underbrace{111 \cdots 11}_{n_k \text{ 번 반복}}, \ k \geq 2 \]

의 $k$번 째 항은 (덧셈에 대한) 지속성 $k$를 가진다.

그렇다면, 주어진 (덧셈에 대한) 지속성 $k$를 가지는 최소의 자연수는 무엇일까? 처음 몇개를 나열해 보면 다음과 같다.

지속성	자연수
1	10
2	19
3	199
4	19,999,999,999,999,999,999,999

지속성 $5$를 갖는 최소의 자연수는 $2 \times 10^{(2 \times 10^{22} − 1)/9} − 1$ 로 주어지는에 이는 $1$ 뒤로 $9$가 $2,222,222,222,222,222,222,222$개 나열된 수이다. 이 수의 각 자릿수를 더하면, 지속성 $4$를 갖는 최소의 수인 $2 \times 10^{22} − 1$를 얻고, 이는 다시 각각 지속성 $3$, $2$, $1$, $0$을 갖는 수 $199$, $19$, $10$, $1$로 변하게 된다. 일반적으로 (덧셈에 대한) 지속성 $k$를 갖는 수의 각 자릿수를 더하면, (덧셈에 대한) 지속성 $k-1$를 갖는 자연수를 얻을 수 있다. 따라서 다음과 같이 일반화 할 수 있다.

따름정리. 아래와 같이 정의된 수열

\[ n_1 = 1, \qquad n_{k+1} = 2 \times 10^{(n_k - 1)/9} − 1, \ k \geq 2 \]

의 $k$번 째 항은 (덧셈에 대한) 지속성 $k$를 갖는 최소의 자연수이다.