Maths Olympiad Prep

Library / HMMO /17 of 56

HMMO, 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
1a∣n={1a∣n0otherwise \mathbf{1}_{a \mid n}= \begin{cases}1 & a \mid n \\ 0 & \text{otherwise}\end{cases}
Then
f(n)2=(12∣n+13∣n+15∣n)2=12∣n+13∣n+15∣n+2(12∣n13∣n+12∣n15∣n+13∣n15∣n)=12∣n+13∣n+15∣n+2(16∣n+110∣n+115∣n) \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 1≤n≤20201 \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,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.