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

英文解析

34. [ 20 ] Find the number of positive integers less than 1000000 that are divisible by some perfect cube
    { }
    greater than 1. Your score will be max 0 , b 20 − 200 | 1 − |c , where k is your answer and S is thekactual answer.S
    Answer: 168089 Using the following code, we get the answer (denoted by the variable ans):
    ans = 0
    for n in xrange(1,1000000):
    divisible_by_cube = Truefor i in xrange(2,101):
    if n%(iii)==0:
    divisible_by_cube = Falsebreakif divisible_by_cube: ans = ans + 1
    print ans
    This gives the output
    168089
    Alternatively, let N = 1000000 and denote by P the set of primes. Then by PIE, the number ofn ∈ (0 , N ) divisible by a nontrivial cube, or equivalently, by p for some p ∈ P , is 3
    ∑ ∑
    N − 1 N − 1
    b c − b c ± · · · ,
    3 3 3
    p p qp ∈ P p<q ∈ Pwhich deviates from
    ∑ ∑ ∏
    N − 1 N − 1 − 3 − ± · · · = ( N − 1)(1 − (1 − p ))
    3 3 3
    p p qp ∈ P p<q ∈ P p ∈ Pby at most the sum of
    N − 1
    1 / 3 1 / 3 1 / 3
    • N sup | t − b t c| = N , for terms b c with p · · · p ≤ ( N − 1) , and
    3 3 1 rt ∈ Rp ··· pr
    ∫ − 2 / 31
    ∑
    ∞
    ( N − 1) − 3 − 1 − 3
    • ( N − 1) k < ( N − 1)[( N − 1) + x dx ] = 1 + ( N − 1) =
    1 / 3
    1 / 3
    k> ( N − 1)
    ( N − 1) 2
    1 / 3
    O ( N ), for the remaining terms.
    ∏
    6 6 − 3
    So we are really interested in 10 − 10 (1 − p ) (which, for completeness, is 168092 . 627 . . . ).
    p ∈ P
    There are a few simple ways to approximate this:
    ∏
    − 3 − 3
    • We can use a partial product of (1 − p ). Using just 1 − 2 = 0 . 875 gives an answer ofp ∈ P
    3 − 3 − 3
    125000 (this is also just the number of x ≤ N divisible by 2 = 8), (1 − 2 )(1 − 3 ) ≈ 0 . 843
    3 3
    gives 157000 (around the number of x divisible by 2 or 3 ), etc. This will give a lower bound,
    of course, so we can guess a bit higher. For instance, while 157000 gives a score of around 7,
    rounding up to 160000 gives ≈ 10.
    ∏
    − 3 − 1 − 3 − 3
    • We can note that (1 − p ) = ζ (3) is the inverse of 1 + 2 + 3 + · · · . This is a bit lessp ∈ P − 3
    efficient, but successive partial sums (starting with 1 + 2 ) give around 111000, 139000, 150000,
    157000, etc. Again, this gives a lower bound, so we can guess a little higher.
    • We can optimize the previous approach with integral approximation after the r th term: ζ (3) is
    ∫ ∫
    ∞ ∞
    − 3 − 3 − 3 − 2 − 31
    the sum of 1 + 2 + · · · + r plus something between x dx = ( r + 1) and x dx =
    r +1 2 r
    1 − 2
    r . Then starting with r = 1, we get intervals of around (111000 , 334000), (152000 , 200000),
    (161000 , 179000), (165000 , 173000), etc. Then we can take something like the average of the two 2
    endpoints as our guess; such a strategy gets a score of around 10 for r = 2 already, and ≈ 17 forr = 3.