2022 AMC 12A Problem 23

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

Small hint:

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}

Big hint:

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}

Solution:

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.