View source for Mock AIME 5 2005-2006 Problems/Problem 1

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

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

<math>\lfloor 99/2\rfloor =49</math>

<math>\lfloor 99/3\rfloor =33</math>

<math>\lfloor 99/5\rfloor =19</math>

<math>\lfloor 99/7\rfloor =14</math>

<math>\lfloor 99/11\rfloor =9</math>

<math>\lfloor 99/13\rfloor =7</math>

<math>\lfloor 99/17\rfloor =5</math>

<math>\lfloor 99/19\rfloor =5</math>

<math>\lfloor 99/23\rfloor =4</math>

<math>\lfloor 99/29\rfloor =3</math>

<math>\lfloor 99/31\rfloor =3</math>

<math>\lfloor 99/37\rfloor =2</math>

<math>\lfloor 99/41\rfloor =2</math>

<math>\lfloor 99/43\rfloor =2</math>

<math>\lfloor 99/47\rfloor =2</math>

So we compute

<cmath>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</cmath>



<cmath>=98+99+95+98+99+91+85+95+92+87+93+74+82+86+94</cmath>



<cmath>=197+193+190+180+179+167+168+94=390+370+346+262</cmath>



<cmath>=760+608=1368</cmath>

Our desired answer then is <cmath>\boxed{368}</cmath>

== See also ==
{{Mock AIME box|year=2005-2006|n=5|source=76847|before=First Question|num-a=2}}

[[Category:Introductory Number Theory Problems]]