HMMT 十一月 2010 · 冲刺赛 · 第 34 题

HMMT November 2010 — Guts Round — Problem 34

[ 25 ] Estimate the sum of all the prime numbers less than 1 , 000 , 000. If the correct answer is X and ( ) 25 X 25 A you write down A , your team will receive min b c , b c points, where b x c is the largest integer A X less than or equal to x . ′

解析

[ 25 ] Estimate the sum of all the prime numbers less than 1 , 000 , 000. If the correct answer is X and ( ) 25 X 25 A you write down A , your team will receive min b c , b c points, where b x c is the largest integer A X less than or equal to x . Answer: 37550402023 A decent approximation to the sum of all the primes can be obtained with n th the following two facts. First, there are approximately primes less than n and second, the n ln n prime is approximately n ln n . We’ll approximate ln 1000000 as 15 (the actual number is 13.8), so 6 10 ∑ 6 10 15 there are approximately primes. Then we want n ln n . If you know calculus, this can be n =1 15 6 ∫ 10 1 2 1 2 15 approximated by the integral x ln x dx , which has the antiderivative x ln x − x , giving an 1 2 4 12 12 1 10 1 10 answer of around · · (15 − ln 15) − · . Estimating ln 15 as about 3, this is approximately 2 225 4 225 12 23 · 10 10 = 2 . 5 · 10 = 25 , 000 , 000 , 000. The actual answer is 37,550,402,023, so an approximation of this 900 accuracy would get 16 points. We can arrive at the same answer without calculus by approximating 6 6 6 6 12 10 10 10 10 2 10 ∑ ∑ ∑ ∑ ∑ ∑ − k n n 1 n n 1 15 15 15 15 225 ln n as , so that our sum becomes = ≈ · = n =1 k =1 k =1 k =1 n = k k =1 k k k 2 k 6 10 ∑ 12 6 12 6 12 1 10 10 1 1 10 10 1 10 10 15 · · ln( ) − k ≈ · · ln( ) − ≈ 2 . 5 · 10 . k =1 2 225 15 2 2 225 15 4 225 ′