Track / Stage 5 / 371 of 400 #971 of 1964

Problem 971

AIME late

Number theory Difficulty 5.9 Prove it

1/2k For $n>1$ , let $d_{t}(n)=d_{t-1}(d(n))=\cdots=d(d(d(\cdots d(n) \cdots))$ .
Prove: The sequence
$d_{1}(n)=d(n), d_{2}(n), d_{3}(n), \cdots$

is eventually always 2. Also, for any given positive integer $m$ , prove that there exists $n$ such that (1) it is 2 from the $m$ -th term onwards.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

When $n>2$ , 1 and $n$ are both positive divisors of $n$ . Since $n-1 \nmid n$ , we have $2 \leqslant d(n)<n$ . Therefore, (1) is a decreasing sequence of natural numbers, which can only have a finite number of distinct terms, meaning from a certain term onward, the terms of (1) become the constant 2.

Also, $d(2)=2$ is the case for $m=1$ . Suppose there exists an $n$ such that the $m$ -th term of (1) starts to be 2. Then, since $d\left(2^{n-1}\right)=n$ , we have $d\left(2^{n-1}\right), d_{2}\left(2^{n-1}\right), \cdots$ starting from the $(m+1)$ -th term, are 2.
Thus, the conclusion holds.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.