Question

设 $h_n$ 和 $k_n$ 是唯一一对互质的正整数，使得

$\frac11+\frac12+\frac13+\cdots+\frac1n=\frac{h_n}{k_n}\text{。}$

设 $L_n$ 表示 $1$ ， $2$ ， $3$ ， $\ldots$ ， $n$ 的最小公倍数。对于多少个满足 $1\le n\le22$ 的整数 $n$ 有 $k_n\lt L_n$ ？

Let $h_n$ and $k_n$ be the unique relatively prime positive integers such that

$\frac11+\frac12+\frac13+\cdots+\frac1n=\frac{h_n}{k_n}.$

Let $L_n$ denote the least common multiple of the numbers $1,$ $2,$ $3,$ $\ldots,$ $n.$ For how many integers $n$ with $1\le n\le22$ is $k_n\lt L_n?$

$0$

$3$

$7$

$8$

$10$

答案：D

知识点：最小公倍数质因数分解模运算

难度评级：2520

小提示：

把 $H_n$ 写成以 $L_n$ 为分母的分数；约分后分母变小，正好意味着有质数从分子 $\sum_k \frac{L_n}{k}$ 中约掉

Writing $H_n$ over $L_n,$ the reduced denominator is smaller exactly when a prime cancels from the numerator $\sum_k \frac{L_n}{k}$

大提示：

对满足 $p^a\le n\lt p^{a+1}$ 的质数幂 $p^a$ 检查 $p$ 是否整除 $\sum_{v_p(k)=a} \frac{L_n}{k}$

For a prime power $p^a$ with $p^a\le n\lt p^{a+1},$ check whether $p$ divides $\sum_{v_p(k)=a} \frac{L_n}{k}$

解答：

$L_n$ 总是 $k_n$ 的倍数，所以 $k_n\lt L_n$ 恰好在某个质数 $p$ 同时整除 $L_n$ 和分子 $N=\sum_{k=1}^n \tfrac{L_n}{k}$ 时成立（即有质数被约掉）。

对具有最大幂 $p^a\le n$ 的质数 $p$ ，只有满足 $v_p(k)=a$ 的项会使 $\frac{L_n}{k}$ 不含 $p$ ，其余项都能被 $p$ 整除。因此 $p$ 被约掉，当且仅当 $\sum_{v_p(k)=a}\tfrac{L_n}{k}\equiv0\pmod p$ 。

利用 $H_n=H_{n-1}+\frac{1}{n}$ 递推应用这个判定，得到：当 $1\le n\le5$ 时， $k_n=L_n$ ；当 $6\le n\le8$ 时， $k_n=\frac{L_n}{3}$ ；当 $9\le n\le17$ 时，再次有 $k_n=L_n$ 。最后，对 $n=18,19,20,21,22$ ，比值 $\frac{L_n}{k_n}$ 分别为 $3,3,15,45,45$ ，因此恰好在 $n=6,7,8,18,19,20,21,22$ 时发生约分，共有 $8$ 个值。

因此，正确答案是 D。

$L_n$ is always divisible by $k_n,$ so $k_n\lt L_n$ exactly when some prime $p$ divides both $L_n$ and the numerator $N=\sum_{k=1}^n \tfrac{L_n}{k}$ (i.e. a prime cancels).

For a prime $p$ with maximal power $p^a\le n,$ only the terms with $v_p(k)=a$ keep $p$ out of $\frac{L_n}{k};$ all others are divisible by $p.$ So $p$ cancels iff $\sum_{v_p(k)=a}\tfrac{L_n}{k}\equiv0\pmod p.$

Applying this test recursively with $H_n=H_{n-1}+\frac{1}{n}$ gives $k_n=L_n$ for $1\le n\le5,$ $k_n=\frac{L_n}{3}$ for $6\le n\le8,$ and $k_n=L_n$ again for $9\le n\le17.$ Finally, the ratios $\frac{L_n}{k_n}$ for $n=18,19,20,21,22$ are $3,3,15,45,45,$ respectively. Thus cancellation occurs precisely for $n=6,7,8,18,19,20,21,22,$ which is $8$ values.

Thus, the correct answer is D.

2022 AMC 12A 第 23 题

答案：D

难度评级：2520

小提示：

大提示：

解答：

其他年份的第 23 题