Mock AIME 5 2005-2006 Problems/Problem 1

Problem

Suppose $n$ is a positive integer. Let $f(n)$ be the sum of the distinct positive prime divisors of $n$ less than $50$ (e.g. $f(12) = 2+3 = 5$ and $f(101) = 0$). Evaluate the remainder when $f(1)+f(2)+\cdots+f(99)$ is divided by $1000$.

Solution

So all of the prime numbers less than $50$ are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,$ and $47$. So we just need to find the number of numbers that are divisible by $2$, the number of numbers divisible by $3$, etc.

$\lfloor 99/2\rfloor =49$

$\lfloor 99/3\rfloor =33$

$\lfloor 99/5\rfloor =19$

$\lfloor 99/7\rfloor =14$

$\lfloor 99/11\rfloor =9$

$\lfloor 99/13\rfloor =7$

$\lfloor 99/17\rfloor =5$

$\lfloor 99/19\rfloor =5$

$\lfloor 99/23\rfloor =4$

$\lfloor 99/29\rfloor =3$

$\lfloor 99/31\rfloor =3$

$\lfloor 99/37\rfloor =2$

$\lfloor 99/41\rfloor =2$

$\lfloor 99/43\rfloor =2$

$\lfloor 99/47\rfloor =2$

So we compute

\[49\times2+33\times3+19\times5+14\times7+9\times11+7\times13+5\times17+5\times19+4\times23+3\times29+3\times31+2\times37+2\times41+2\times43+2\times47\]


\[=98+99+95+98+99+91+85+95+92+87+93+74+82+86+94\]


\[=197+193+190+180+179+167+168+94=390+370+346+262\]


\[=760+608=1368\]

Our desired answer then is \[\boxed{368}\]

See also

Mock AIME 5 2005-2006 (Problems, Source)
Preceded by
First Question
Followed by
Problem 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15