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

英文解析

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 Ayou write down A , your team will receive min b c , b c points, where b x c is the largest integer
    A Xless than or equal to x .
    Answer: 37550402023 A decent approximation to the sum of all the primes can be obtained withnthe following two facts. First, there are approximately primes less than n and second, the nthln nprime is approximately n ln n . We’ll approximate ln 1000000 as 15 (the actual number is 13.8), so
    ∑106
    15106
    there are approximately primes. Then we want n ln n . If you know calculus, this can ben =1
    ∫ 10615
    1 2 1 2
    approximated by the integral x ln x dx , which has the antiderivative x ln x − x , giving an 15
    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
    23 · 1012 = 2 . 5 · 10 = 25 , 000 , 000 , 000. The actual answer is 37,550,402,023, so an approximation of this 10
    accuracy would get 16 points. We can arrive at the same answer without calculus by approximating 900
    6 6 6 6
    10 10 10 10 212
    ∑ ∑ ∑ ∑ ∑ ∑10 − kn n
    1 n n 1
    15 15 15 15
    ln n as , so that our sum becomes = ≈ · =225
    n =1
    k =1 k =1 k =1 n = k k =1
    k k k 2 k
    ∑106
    12 6 12 6 12
    1 10 10 1 1 10 10 1 10 10
    · · ln( ) − k ≈ · · ln( ) − ≈ 2 . 5 · 10 .15
    k =1
    2 225 15 2 2 225 15 4 225
    ′