如 $n$ 是不小于 $3$ 的自然数，以 $f(n)$ 表示不是 $n$ 的因数的最小自然数（例如 $f(12)=5$）．如果 $f(n)\geqslant 3$，又可作 $f(f(n))$．类似地，如果 $f(f(n))\geqslant 3$，又可作 $f(f(f(n)))$ 等．如果 $\underbrace{f\left( f\left( \cdots f\right. \right.}_{k个f}\left( n \right)\left. \left. \cdots \right) \right)=2$，就把 $k$ 叫做 $n$ 的"长度"．
如果用 $l_n$ 表示 $n$ 的长度，试对任意的自然数 $n(n \geqslant 3)$ 求 $l_n$，并证明你的结论．
如果用 $l_n$ 表示 $n$ 的长度，试对任意的自然数 $n(n \geqslant 3)$ 求 $l_n$，并证明你的结论．
【难度】
【出处】
1988第3届CMO试题
【标注】
【答案】
略
【解析】
由假设，$f(n)$ 表示不是 $n$ 的因数的最小自然数．先证明对任何 $n(n \geqslant 3)$，$f(n)$ 不会是两个素数的（$\geqslant 2$ 的）数的乘积．用反证法，设 $f(n)=p \cdot q$（其中 $p, q \geqslant 2,(p, q)=1$），由 $f$ 的定义，$p,q$ 都是 $n$ 的因数，即 $p|n, q| n$，由 $(p, q)=1$，所以 $p q | n$，与 $f(n)=p q$ 矛盾．由于 $f(n)$ 不会是两个互素的（$\geqslant 2$ 的）数的乘积，因而 $f(n)$ 必为 $p^{k}$ 形成的数，其中 $p$ 是素数，$k$ 是自然数（实际上，$f$ 的值域是这种形式上的数的全体）．由此，对于 $n\geqslant 3$ 的自然数 $n$，或者 $f(n)=2$（易见这当且仅当 $n$ 为奇数时成立），或者 $f(n)=2^{k}(k \geqslant 2)$，这时 $f(f(n))=3$，从而 $n$ 的长度为 $3$，此外 $f(n)=p^{k}$（$p$ 是素奇数，$k\geqslant 1$），这时 $n$ 的长度为 $2$．由此，$n$ 的长度 $l_n$ 由 $n$ 的特性所决定：
$l_n=\begin{cases}
1,当n是奇数\\
3,有大于1的自然数k,使得对于任何小于2^k的素数p及满足p^j<2^k的自然数j,p^j|n,而且2^k\not |n\\
2,其他情况\\
\end{cases}$
$l_n=\begin{cases}
1,当n是奇数\\
3,有大于1的自然数k,使得对于任何小于2^k的素数p及满足p^j<2^k的自然数j,p^j|n,而且2^k\not |n\\
2,其他情况\\
\end{cases}$
答案
解析
备注
