Maths Olympiad Prep

Library / /245 of 348

Number theory Difficulty 5.0 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Define 1an={1an0 otherwise \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 1 for each time nn is divisible by 2,3, or 5, and additionally summing 2 for each time nn is divisible by 6,10, or 15. 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.