HMMT 十一月 2013 · 冲刺赛 · 第 34 题
HMMT November 2013 — Guts Round — Problem 34
题目详情
- [ 20 ] Find the number of positive integers less than 1000000 that are divisible by some perfect cube { } k greater than 1. Your score will be max 0 , b 20 − 200 | 1 − |c , where k is your answer and S is the S actual answer.
解析
- [ 20 ] Find the number of positive integers less than 1000000 that are divisible by some perfect cube { } k greater than 1. Your score will be max 0 , b 20 − 200 | 1 − |c , where k is your answer and S is the S actual answer. 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 = True for i in xrange(2,101): if n%(iii)==0: divisible_by_cube = False break if 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 of 3 n ∈ (0 , N ) divisible by a nontrivial cube, or equivalently, by p for some p ∈ P , is ∑ ∑ N − 1 N − 1 b c − b c ± · · · , 3 3 3 p p q p ∈ P p<q ∈ P which deviates from ∑ ∑ ∏ N − 1 N − 1 − 3 − ± · · · = ( N − 1)(1 − (1 − p )) 3 3 3 p p q p ∈ P p<q ∈ P p ∈ P by 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 r t ∈ R p ··· p r 1 ∫ − 2 / 3 ∑ ∞ ( 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 of p ∈ 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 less p ∈ 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 ∫ ∫ ∞ ∞ 1 − 3 − 3 − 3 − 2 − 3 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), 2 (161000 , 179000), (165000 , 173000), etc. Then we can take something like the average of the two endpoints as our guess; such a strategy gets a score of around 10 for r = 2 already, and ≈ 17 for r = 3.