Maths Olympiad Prep

Track / Stage 6 / 195 of 400 #1195 of 1964

Problem 1195

National olympiad, first round
Number theory Difficulty 6.3 Prove it

621n6 \cdot 21 n is a natural number not less than 3, f(n)f(n) represents the smallest natural number that is not a divisor of nn (for example, f(12)=5f(12)=5). If f(n)3f(n) \geqslant 3, then f(f(n))f(f(n)) can also be made. Similarly, if f(f(n))3f(f(n)) \geqslant 3, then f(f(f(n)))f(f(f(n))) can also be made, and so on. If
f(f(fk f’s(n)))=2, \underbrace{f(f(\cdots f}_{k \text { f's}}(n) \cdots))=2,

then kk is called the "length" of nn.
If lnl_{n} represents the length of nn, try to find lnl_{n} for any natural number n(n3)n(n \geqslant 3), and prove your conclusion.

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

[Solution] For natural number nn, we discuss by cases.
Case 11: nn is odd.
In this case, f(n)=2f(n)=2, so ln=1l_{n}=1.
Case 22: nn is even.
In this case, we set n=2a(2m+1)n=2^{a}(2 m+1), where a1,m0a \geqslant 1, m \geqslant 0.
If all odd numbers tt satisfying 1<t<2a+11<t<2^{a+1} are divisors of nn, then
f(n)=2a+1,f(f(n))=3,f(f(f(n)))=2. \begin{array}{l} f(n)=2^{a+1}, \\ f(f(n))=3, \\ f(f(f(n)))=2 . \end{array}

Therefore, ln=3\quad l_{n}=3.
If not all odd numbers tt satisfying 1<t<2a+11<t<2^{a+1} are divisors of nn, then there must be a smallest positive odd number t0(1<t0<2a+1)t_{0}\left(1<t_{0}<2^{a+1}\right) that is not a divisor of nn. Thus we have
f(n)=t0,f(f(n))=f(t0)=2. \begin{array}{l} f(n)=t_{0}, \\ f(f(n))=f\left(t_{0}\right)=2 . \end{array}

Therefore, ln=2l_{n}=2.
In summary, we have
ln={1,n is odd, 3,n is even 2a(2m+1),a1,m0, and all odd numbers t satisfying 1<t<2a+1 are divisors of n,2,n is even 2a(2m+1),a1,m0, and there exists an odd number t0 that is not a divisor of n, satisfying 1<t0<2a+1. l_{n}=\left\{\begin{array}{l} 1, n \text { is odd, } \\ 3, n \text { is even } 2^{a}(2 m+1), a \geqslant 1, m \geqslant 0, \\ \quad \text { and all odd numbers } t \text { satisfying } 1<t<2^{a+1} \text { are divisors of } n, \\ 2, n \text { is even } 2^{a}(2 m+1), a \geqslant 1, m \geqslant 0, \\ \text { and there exists an odd number } t_{0} \text { that is not a divisor of } n, \text { satisfying } 1<t_{0}<2^{a+1} . \end{array}\right.

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