Question

在正整数上定义函数 $f_1$ ，令 $f_1(1) = 1$ 。若 $n \gt 1$ 的质因数分解为 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ ，则 $\begin{aligned} &f_1(n) = (p_1 + 1)^{e_1 - 1}(p_2 + 1)^{e_2 - 1} \\ &\quad \cdots (p_k + 1)^{e_k - 1}\text{。} \end{aligned}$ 对每个 $m \ge 2$ ，令 $f_m(n) = f_1(f_{m-1}(n))$ 。在范围 $1 \le N \le 400$ 中，有多少个 $N$ 使序列 $(f_1(N), f_2(N), f_3(N), \ldots)$ 无界？注：一个正数序列无界是指对每个整数 $B$ ，都存在该序列中的一项大于 $B$ 。

Define the function $f_1$ on the positive integers by setting $f_1(1) = 1$ and if $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ is the prime factorization of $n \gt 1,$ then $\begin{aligned} &f_1(n) = (p_1 + 1)^{e_1 - 1}(p_2 + 1)^{e_2 - 1} \\ &\quad \cdots (p_k + 1)^{e_k - 1}. \end{aligned}$ For every $m \ge 2,$ let $f_m(n) = f_1(f_{m-1}(n)).$ For how many $N$ in the range $1 \le N \le 400$ is the sequence $(f_1(N), f_2(N), f_3(N), \ldots)$ unbounded? Note: a sequence of positive numbers is unbounded if for every integer $B,$ there is a member of the sequence greater than $B.$

$15$

$16$

$17$

$18$

$19$

答案：D

知识点：质因数分解整除性递推

难度评级：2520

小提示：

若 $N_2$ 是 $N_1$ 的倍数，则 $f_1(N_2)$ 是 $f_1(N_1)$ 的倍数，所以无界性会传递给倍数；找出最小的“本质” $N$

If $N_2$ is a multiple of $N_1$ then $f_1(N_2)$ is a multiple of $f_1(N_1),$ so unboundedness is inherited by multiples; find the minimal “essential” $N$

大提示：

一个本质的 $N$ 每个指数都至少为 $2$ ，且至多含两个质因数；先分析 $2,3$ 的幂，再分析 $400$ 以内剩下的少数质数幂和质数对

An essential $N$ has every exponent at least $2$ and at most two prime factors; analyze powers of $2,3$ first, then the few remaining prime powers and prime pairs below $400$

解答：

若 $N_2$ 是 $N_1$ 的倍数，则 $f_1(N_2)$ 是 $f_1(N_1)$ 的倍数，所以若 $S_{N_1}$ 无界，则 $S_{N_2}$ 也无界。称 $N$ 为本质数，如果它无界而任何真因数都不无界。本质数 $N$ 的所有指数都至少为 $2$ ，并且 $(p_1\cdots p_k)^2\le400$ 迫使它至多含两个质数。

对于 $n=2^a3^b$ ，两次迭代把指数对变成 $(2a-4,2b-3)$ 。因此轨道无界，当且仅当 $a\ge5$ 或 $b\ge4$ ，由此得到本质数 $2^5=32$ 和 $3^4=81$ 。对于只含另一个质数的情形，上界只留下 $5^2,5^3,7^2,7^3,11^2,13^2,17^2,19^2$ ；直接应用 $f_1$ 后只有 $7^3=343$ 是本质数。对于两个质数， $p_1p_2\le20$ 除 $(2,3)$ 外只留下 $(2,5),(2,7),(3,5)$ 。对相应的平方因子乘积应用 $f_1$ ，只剩 $2^4\cdot5^2=400$ 。

它们在 $400$ 以内的倍数个数分别为 $\lfloor\frac{400}{32}\rfloor=12$ ， $\lfloor\frac{400}{81}\rfloor=4$ ， $\lfloor\frac{400}{343}\rfloor=1$ ，和 $\lfloor\frac{400}{400}\rfloor=1$ ，且没有重叠，总数为 $12+4+1+1=18$ 。

因此，正确答案是 D。

If $N_2$ is a multiple of $N_1$ then $f_1(N_2)$ is a multiple of $f_1(N_1),$ so if $S_{N_1}$ is unbounded so is $S_{N_2}.$ Call $N$ essential if it is unbounded but no proper divisor is. An essential $N$ must have all exponents at least $2,$ and $(p_1\cdots p_k)^2\le400$ forces at most two primes.

For $n=2^a3^b,$ two iterations send the exponent pair to $(2a-4,2b-3).$ Thus the orbit is unbounded exactly when $a\ge5$ or $b\ge4,$ producing the essential values $2^5=32$ and $3^4=81.$ For a single other prime, the bound leaves only $5^2,5^3,7^2,7^3,11^2,13^2,17^2,19^2;$ direct application of $f_1$ leaves only $7^3=343$ essential. With two primes, $p_1p_2\le20$ leaves the pairs $(2,5),(2,7),(3,5)$ besides $(2,3).$ Applying $f_1$ to their possible squareful products leaves only $2^4\cdot5^2=400.$

Their multiples up to $400$ number $\lfloor\frac{400}{32}\rfloor=12,$ $\lfloor\frac{400}{81}\rfloor=4,$ $\lfloor\frac{400}{343}\rfloor=1,$ and $\lfloor\frac{400}{400}\rfloor=1,$ with no overlaps, for a total of $12+4+1+1=18.$

Thus, the correct answer is D.

2012 AMC 12B 第 24 题

答案：D

难度评级：2520

小提示：

大提示：

解答：

其他年份的第 24 题