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．