Với mỗi số nguyên dương $n$, ta ký hiệu $d(n)$ là ước số lẻ lớn nhất của $n$
Hàm số $f: \mathbb{N}^{*} \to \mathbb{N}^{*}$ thỏa mãn:
$f(2n-1) = 2^n ; f(2n) = n + \frac{2n}{d(n)}$ với mọi $n \in \mathbb{N}^{*}$
Tìm tất cả các số nguyên dương $k$ sao cho : $ f^k (1) = f(f(...(f(1))...) = 1997$ ($k$ lần lặp $f$)
Dễ dàng tính được với số $y$ lẻ thì $f(2^xy)=2^{x-1}(y+2)$. Do vậy sau $x$ lần tác động $f$ vào số chẵn $2^xy$ thì ta mới thu được số lẻ (số lẻ đó là $y+2x$).
$$2^xy\overset{f}{\longrightarrow}2^{x-1}(y+2)\overset{f}{\longrightarrow}\cdots\overset{f}{\longrightarrow}y+2x$$
Từ nhận xét trên ta thu được: cần $m+1$ lần tác động $f$ vào số lẻ $2m-1$ thì ta mới thu được số lẻ tiếp theo (số lẻ đó là $2m+1$).
$$2m-1\overset{f}{\longrightarrow}2^m\overset{f}{\longrightarrow}\cdots\overset{f}{\longrightarrow}2m+1$$
Với nhận xét này ta thấy rằng khi bắt đầu bởi số lẻ $1$ thì sẽ tồn tại duy nhất $k$ sao cho $f^k(1)=1997$ (vì các số lẻ thu được sau các lần tác động $f$ tăng dần).
$$1\overset{2}{\longrightarrow}3\overset{3}{\longrightarrow}\cdots\overset{999}{\longrightarrow}1997$$
Vậy $k=2+3+\dots+999=\frac{999\cdot 1000}{2}-1=499499$.