Maths Olympiad Prep

Library / /499 of 740

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, dnad\sum_{d \mid n} a_{d} and dnbd\sum_{d \mid n} b_{d} are multiplicative.

We consider the sum dpkad\sum_{d \mid p^{k}} a_{d} and dpkbd\sum_{d \mid p^{k}} b_{d}. Notice that for d=pld=p^{l}, ad=pl/2a_{d}=p^{\lfloor l / 2\rfloor} and bd=p2{l/2}b_{d}=p^{2\{l / 2\}}, so
dpkad=2(p(k+1)/21p1) and dpkbd=(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
dpkad=(p(k+2)/2+pk/22p1) and dpkbd=(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!=2732578!=2^{7} \cdot 3^{2} \cdot 5 \cdot 7, so
d8!ad=(2(161)21)(9+3231)(1+1)(1+1)=30522=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
d8!bd=(382)(1+422)(1+5)(1+7)=12568=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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