Number theory › Divisibility › Assorted divisibility puzzles

Integers reaching one in twenty steps

High school · ●●●●○ 100 pts

For every positive integer

x

, let

f(x)=\begin{cases}1 & \text{if }x = 1\\ \frac x{10} & \text{if }x\text{ is divisible by }10\\ x+1 & \text{otherwise}\end{cases}

and define a sequence by

x_1=x

and

x_{n+1}=f(x_n)

for all positive integers

n

. Let

d(x)

be the smallest

n

such that

x_n=1

. (For example,

d(100)=3

and

d(87)=7

.) Let

m

be the number of positive integers

x

such that

d(x)=20

. Find the sum of the distinct prime factors of

m

.

recurrence relations prime factorisation counting