Maths Olympiad Prep

Library / HMMT November /442 of 672

HMMT November

Number theory Difficulty 5.1 AIME, harder Find the answer United States

Problem:

Mark writes the expression d\sqrt{d} for each positive divisor dd of 8!8! on the board. Seeing that these expressions might not be worth points on HMMT, Rishabh simplifies each expression to the form aba \sqrt{b}, where aa and bb are integers such that bb is not divisible by the square of a prime number. (For example, 20\sqrt{20}, 16\sqrt{16}, and 6\sqrt{6} simplify to 252 \sqrt{5}, 414 \sqrt{1}, and 161 \sqrt{6}, respectively.) Compute the sum of a+ba+b across all expressions that Rishabh writes.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Let n\sqrt{n} simplify to anbna_{n} \sqrt{b_{n}}. Notice that both ana_{n} and bnb_{n} are multiplicative. Thus, ∑d∣nad\sum_{d \mid n} a_{d} and ∑d∣nbd\sum_{d \mid n} b_{d} are multiplicative.

We consider the sum ∑d∣pkad\sum_{d \mid p^{k}} a_{d} and ∑d∣pkbd\sum_{d \mid p^{k}} b_{d}. Notice that for d=pld=p^{l}, ad=p⌊l/2⌋a_{d}=p^{\lfloor l / 2\rfloor} and bd=p2{l/2}b_{d}=p^{2\{l / 2\}}, so
∑d∣pkad=2(p(k+1)/2−1p−1) and ∑d∣pkbd=(p+1)(k+1)2 \sum_{d \mid p^{k}} a_{d}=2\left(\frac{p^{(k+1) / 2}-1}{p-1}\right) \quad \text{ and } \quad \sum_{d \mid p^{k}} b_{d}=\frac{(p+1)(k+1)}{2}
for odd kk, while
∑d∣pkad=(p(k+2)/2+pk/2−2p−1) and ∑d∣pkbd=(p+1)k2+1 \sum_{d \mid p^{k}} a_{d}=\left(\frac{p^{(k+2) / 2}+p^{k / 2}-2}{p-1}\right) \quad \text{ and } \quad \sum_{d \mid p^{k}} b_{d}=\frac{(p+1) k}{2}+1
for even kk.

Notice 8!=27⋅32⋅5⋅78!=2^{7} \cdot 3^{2} \cdot 5 \cdot 7, so
∑d∣8!ad=(2(16−1)2−1)(9+3−23−1)(1+1)(1+1)=30⋅5⋅2⋅2=600 \sum_{d \mid 8!} a_{d}=\left(\frac{2(16-1)}{2-1}\right)\left(\frac{9+3-2}{3-1}\right)(1+1)(1+1)=30 \cdot 5 \cdot 2 \cdot 2=600
and
∑d∣8!bd=(3⋅82)(1+4⋅22)(1+5)(1+7)=12⋅5⋅6⋅8=2880 \sum_{d \mid 8!} b_{d}=\left(\frac{3 \cdot 8}{2}\right)\left(1+\frac{4 \cdot 2}{2}\right)(1+5)(1+7)=12 \cdot 5 \cdot 6 \cdot 8=2880
so the sum of ad+bda_{d}+b_{d} would be 600+2880=3480600+2880=3480.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.