Question

如n是不小于3的自然數，以f(n)表示不是n的因數的最小自然數(例如f(12)＝5)．如果f(n)≥3，又可作f(f(n))．類似地，如果f(f(n))≥3，又可作f(f(f(n)))

果用L_n表示n的長度，試對任意的自然數n(n≥3)，求L_n并證明你的結論．

Answer 1

解析：很明顯，若奇數n≥3，那么f(n)＝2，因此只須討論n為偶數的情況，我們首先證明，對任何n≥3，f(n)＝p^s，這里P是素數，s為正整數．假若不然，若f(n)有兩個不同的素因子，這時總可以將f(n)表為f(n)＝ab，其中a、b是大于1的互素的正整數．由f的定義知，a與b都應能整除n，因(a，b)＝1，故ab也應整除n，這與f(n)＝ab矛盾．所以f(n)＝p^s．

由此可以得出以下結論：

(1)當n為大于1的奇數時，f(n)＝2，故L_n＝1；

(2)設n為大于2的偶數，如果f(n)＝奇數，那么f(f(n))＝2，這時L_n＝2；如果f(n)＝2^s，其中自然數s≥2，那么f(f(n))＝f(2^s)＝3，從而f(f(f(n)))＝f(3)＝2，這時L_n＝3．