Question

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$

Answer: D

Concepts:least common multiple prime factorization modular arithmetic

Difficulty rating: 2520

Solution:

Always $k_n\mid L_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 $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}+1/n$ gives $k_n=L_n$ for $1\le n\le5,$ $k_n=L_n/3$ for $6\le n\le8,$ and $k_n=L_n$ again for $9\le n\le17.$ Finally, the ratios $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 Problem 23

Answer: D

Difficulty rating: 2520

Solution:

Problem 23 in Other Years