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

문제 소개

이 문제는 마틴 가드너 (Martin Gardner)의 책 "The Colossal Book of Short Puzzles and Problems"에 수록되어 있는 문제 중에 하나이다. 이 책은 수많은 수학 퍼즐 및 문제들을 몇 가지의 분야로 분류한 뒤, 분류된 문제들의 난이도에 따라 난이도 순서로 수록하고 있는데, 이 문제는 "Numbers" 분야에서 가장 마지막에 수록된 문제이다. (따라서, "Numbers" 분야에 포함시킨 문제들 중에 마틴 가드너는 이 문제를 가장 어렵다고 생각했을 것이다.) 문제는 다음과 같다.

A number's persistence is the number of steps required to reduce it to a single digit by multiplying all its digits to obtain a second number, then multiplying all the digits of that number to obtain a third number, and so on until a one-digit number is obtained. For example, 77 has a persistence of four because it requires four steps to reduce it to one digit: 77-49-36-18-8. The smallest number of persistence one is 10, the smallest of persistence two is 25, the smallest of persistence three is 39, and the smaller of persistence four is 77. What is the smallest number of persistence five?

숫자의 지속성이란 주어진 수의 각 자릿수들을 곱하여 두번째 수를 만들고, 다시 두번째 수의 각 자릿수들을 곱하여 세번째 수를 만들고... 하는 과정을 반복하여, 주어진 곱의 결과가 한자리의 수가 될 때까지 반복한 이 과정의 횟수를 말한다. 예를 들어 77은 네 단계를 거쳐서 77 → 49 → 36 → 18 → 8 과 같이 한자리 수가 되므로, 지속성 4를 가진다. 지속성 1을 가지는 가장 작은 수는 10이다. 또한 지속성 2를 갖는 가장 작은 수는 25이고, 지속성 3을 갖는 가장 작은 수는 39이며, 지속성 4를 갖는 가장 작은 수는 77이다. 그러면 지속성 5를 갖는 가장 작은 수는 무엇일까?

숫자의 지속성: 1부터 100까지

우선 1부터 9까지의 수는 (이미 한자리 수이기 때문에) 당연히 지속성이 0이 된다. 따라서 숫자의 지속성은 10 이상의 수 부터 의미가 있을 것이다. 또한 주어진 수의 자릿수 중에 0이 포함되면, 이 수의 지속성은 1이 된다는 사실도 쉽게 알 수 있다. 아래에 10부터 100까지 수들의 지속성 및 그 계산 과정을 정리해 보았다. (아래 더보기를 클릭하면 전체 내용을 볼 수 있다.) 아래의 결과를 보면 알겠지만 모든 숫자들의 지속성이 4 이하이기 때문에 문제의 정답은 최소 100 이상의 수가 된다는 것을 알 수 있다. 또한 10부터 100까지의 수 중에서 지속성 4를 갖는 수는 77이 유일하다는 사실도 확인할 수 있다.

Terminated in 1 step(s): 10 → 0

Terminated in 1 step(s): 11 → 1

Terminated in 1 step(s): 12 → 2

Terminated in 1 step(s): 13 → 3

Terminated in 1 step(s): 14 → 4

Terminated in 1 step(s): 15 → 5

Terminated in 1 step(s): 16 → 6

Terminated in 1 step(s): 17 → 7

Terminated in 1 step(s): 18 → 8

Terminated in 1 step(s): 19 → 9

Terminated in 1 step(s): 20 → 0

Terminated in 1 step(s): 21 → 2

Terminated in 1 step(s): 22 → 4

Terminated in 1 step(s): 23 → 6

Terminated in 1 step(s): 24 → 8

Terminated in 2 step(s): 25 → 10 → 0

Terminated in 2 step(s): 26 → 12 → 2

Terminated in 2 step(s): 27 → 14 → 4

Terminated in 2 step(s): 28 → 16 → 6

Terminated in 2 step(s): 29 → 18 → 8

Terminated in 1 step(s): 30 → 0

Terminated in 1 step(s): 31 → 3

Terminated in 1 step(s): 32 → 6

Terminated in 1 step(s): 33 → 9

Terminated in 2 step(s): 34 → 12 → 2

Terminated in 2 step(s): 35 → 15 → 5

Terminated in 2 step(s): 36 → 18 → 8

Terminated in 2 step(s): 37 → 21 → 2

Terminated in 2 step(s): 38 → 24 → 8

Terminated in 3 step(s): 39 → 27 → 14 → 4

Terminated in 1 step(s): 40 → 0

Terminated in 1 step(s): 41 → 4

Terminated in 1 step(s): 42 → 8

Terminated in 2 step(s): 43 → 12 → 2

Terminated in 2 step(s): 44 → 16 → 6

Terminated in 2 step(s): 45 → 20 → 0

Terminated in 2 step(s): 46 → 24 → 8

Terminated in 3 step(s): 47 → 28 → 16 → 6

Terminated in 2 step(s): 48 → 32 → 6

Terminated in 3 step(s): 49 → 36 → 18 → 8

Terminated in 1 step(s): 50 → 0

Terminated in 1 step(s): 51 → 5

Terminated in 2 step(s): 52 → 10 → 0

Terminated in 2 step(s): 53 → 15 → 5

Terminated in 2 step(s): 54 → 20 → 0

Terminated in 3 step(s): 55 → 25 → 10 → 0

Terminated in 2 step(s): 56 → 30 → 0

Terminated in 3 step(s): 57 → 35 → 15 → 5

Terminated in 2 step(s): 58 → 40 → 0

Terminated in 3 step(s): 59 → 45 → 20 → 0

Terminated in 1 step(s): 60 → 0

Terminated in 1 step(s): 61 → 6

Terminated in 2 step(s): 62 → 12 → 2

Terminated in 2 step(s): 63 → 18 → 8

Terminated in 2 step(s): 64 → 24 → 8

Terminated in 2 step(s): 65 → 30 → 0

Terminated in 3 step(s): 66 → 36 → 18 → 8

Terminated in 2 step(s): 67 → 42 → 8

Terminated in 3 step(s): 68 → 48 → 32 → 6

Terminated in 3 step(s): 69 → 54 → 20 → 0

Terminated in 1 step(s): 70 → 0

Terminated in 1 step(s): 71 → 7

Terminated in 2 step(s): 72 → 14 → 4

Terminated in 2 step(s): 73 → 21 → 2

Terminated in 3 step(s): 74 → 28 → 16 → 6

Terminated in 3 step(s): 75 → 35 → 15 → 5

Terminated in 2 step(s): 76 → 42 → 8

Terminated in 4 step(s): 77 → 49 → 36 → 18 → 8

Terminated in 3 step(s): 78 → 56 → 30 → 0

Terminated in 3 step(s): 79 → 63 → 18 → 8

Terminated in 1 step(s): 80 → 0

Terminated in 1 step(s): 81 → 8

Terminated in 2 step(s): 82 → 16 → 6

Terminated in 2 step(s): 83 → 24 → 8

Terminated in 2 step(s): 84 → 32 → 6

Terminated in 2 step(s): 85 → 40 → 0

Terminated in 3 step(s): 86 → 48 → 32 → 6

Terminated in 3 step(s): 87 → 56 → 30 → 0

Terminated in 3 step(s): 88 → 64 → 24 → 8

Terminated in 3 step(s): 89 → 72 → 14 → 4

Terminated in 1 step(s): 90 → 0

Terminated in 1 step(s): 91 → 9

Terminated in 2 step(s): 92 → 18 → 8

Terminated in 3 step(s): 93 → 27 → 14 → 4

Terminated in 3 step(s): 94 → 36 → 18 → 8

Terminated in 3 step(s): 95 → 45 → 20 → 0

Terminated in 3 step(s): 96 → 54 → 20 → 0

Terminated in 3 step(s): 97 → 63 → 18 → 8

Terminated in 3 step(s): 98 → 72 → 14 → 4

Terminated in 2 step(s): 99 → 81 → 8

Terminated in 1 step(s): 100 → 0 

더 생각해볼 만한 문제

숫자의 지속성에 관해 추가적으로 다음과 같은 질문들을 생각해 볼 수 있다.

• 주어진 수에 대하여 그 수의 지속성을 수하는 일반적인 규칙이 존재할까? 

• 위 문제에 대한 역을 생각해 보자. 주어진 자연수 k에 대하여, k를 지속성 가지는 가장 작은 자연수를 구하는 일반적인 규칙이 존재할까?

• 일반적으로 수가 커질 수록 그 수의 지속성도 커지게 된다. 그렇다면, 이 숫자의 지속성이 무한히 커질 수 있을까? 다시말해 모든 자연수 k에 대하여, 이 수를 지속성으로 가지는 적당히 큰 자연수 N이 항상 존재할까?

• 만약 위의 질문에 대한 답이 거짓이라면, 어떤 자연수 k가 존재해서 모든 자연수들의 지속성이 k보다 작아지게 할 수 있을 것이다. 만약에 그렇다면, 이 수 k의 최솟값은 무엇일까? 좀더 약한 결과로서 k값의 하한(lower bound)을 구할 수 있을까?

• 곱셈이 다닌 덧셈의 지속성에 대해서도 생각해 볼 수 있다. 덧셈에 대한 숫자의 지속성을 주어진 수의 각 자릿수들을 더하여 두번째 수를 만들고, 다시 두번째 수의 각 자릿수들을 더하여 세번째 수를 만들고... 하는 과정을 반복하여, 주어진 곱의 결과가 한자리의 수가 될 때까지 반복한 이 과정의 횟수로 정의하자. 그러면, 77의 경우 77 → 14 → 5 가 되어 (덧셈에 대한) 지속성은 2가 됨을 알 수 있다. 좀 더 계산을 해 보면, (덧셈에 대한) 지속성 2를 갖는 최소의 수는 19이고, 지속성 3을 갖는 최소의 수는 199임을 알 수 있다. 그러면, (덧셈에 대한) 지속성 4와 5를 갖는 최소의 수는 각각 무엇일까?