Maths Olympiad Prep

Library / /22 of 62

, 2020

Number theory Difficulty 4.7 AIME Find the answer United States

Problem:
Let f(n)f(n) be the number of distinct prime divisors of nn less than 66. Compute
n=12020f(n)2 \sum_{n=1}^{2020} f(n)^2

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

Solution

Solution:
Define
1an={1an0otherwise \mathbf{1}_{a \mid n}= \begin{cases}1 & a \mid n \\ 0 & \text{otherwise}\end{cases}
Then
f(n)2=(12n+13n+15n)2=12n+13n+15n+2(12n13n+12n15n+13n15n)=12n+13n+15n+2(16n+110n+115n) \begin{aligned} f(n)^2 & =\left(\mathbf{1}_{2 \mid n}+\mathbf{1}_{3 \mid n}+\mathbf{1}_{5 \mid n}\right)^2 \\ & =\mathbf{1}_{2 \mid n}+\mathbf{1}_{3 \mid n}+\mathbf{1}_{5 \mid n}+2\left(\mathbf{1}_{2 \mid n} \mathbf{1}_{3 \mid n}+\mathbf{1}_{2 \mid n} \mathbf{1}_{5 \mid n}+\mathbf{1}_{3 \mid n} \mathbf{1}_{5 \mid n}\right) \\ & =\mathbf{1}_{2 \mid n}+\mathbf{1}_{3 \mid n}+\mathbf{1}_{5 \mid n}+2\left(\mathbf{1}_{6 \mid n}+\mathbf{1}_{10 \mid n}+\mathbf{1}_{15 \mid n}\right) \end{aligned}
So summing f(n)2f(n)^2 over integers 1n20201 \leq n \leq 2020 is the same as summing 11 for each time nn is divisible by 22, 33, or 55, and additionally summing 22 for each time nn is divisible by 66, 1010, or 1515.

n=12020f(n)2=20202+20203+20205+2(20206+202010+202015)=1010+673+404+2(336+202+134)=3431\begin{aligned} \sum_{n=1}^{2020} f(n)^2 & =\left\lfloor\frac{2020}{2}\right\rfloor+\left\lfloor\frac{2020}{3}\right\rfloor+\left\lfloor\frac{2020}{5}\right\rfloor+2\left(\left\lfloor\frac{2020}{6}\right\rfloor+\left\lfloor\frac{2020}{10}\right\rfloor+\left\lfloor\frac{2020}{15}\right\rfloor\right) \\ & =1010+673+404+2(336+202+134)=3431 \end{aligned}

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.