HMMT 二月 2021 · 冲刺赛 · 第 34 题
HMMT February 2021 — Guts Round — Problem 34
题目详情
- [20] Let f ( n ) be the largest prime factor of n . Estimate ⌊ ⌋ 6 ( ) ∑ 10 2 f n − 1 4 n =2 N = 10 · . ∑ 6 10 f ( n ) n =2 ( ⌊ ⌋) ( ) 1 / 3 | E − N | An estimate of E will receive max 0 , 20 − 20 points. 3 10
解析
- [20] Let f ( n ) be the largest prime factor of n . Estimate ⌊ ⌋ ( ) 6 ∑ 10 2 f n − 1 4 n =2 N = 10 · . ∑ 6 10 f ( n ) n =2 ( ⌊ ⌋) ( ) 1 / 3 | E − N | An estimate of E will receive max 0 , 20 − 20 points. 3 10 Proposed by: Carl Schildkraut Answer: 18215 Solution: We remark that 2 f ( n − 1) = max( f ( n − 1) , f ( n + 1)) . 6 Let X be a random variable that evaluates to f ( n ) for a randomly chosen 2 ≤ n ≤ 10 ; we essentially want to estimate E [max( X , X )] 1 2 E [ X ] 3 where X denotes a variable with distribution identical to X (this is assuming that the largest prime i factors of n − 1 and n + 1 are roughly independent). 6 A crude estimate can be compiled by approximating that f ( n ) is roughly 10 whenever n is prime and 1 0 otherwise. Since a number in this interval should be prime with ”probability” , we may replace 6 ln 10 1 1 each X with a Bernoulli random variable that is 1 with probability ∼ and 0 otherwise. This 6 i ln 10 14 gives us an estimate of 2 · 14 − 1 1 · 27 2 14 = . 1 14 14 However, this estimate has one notable flaw: n − 1 and n +1 are more likely to share the same primality than arbitrarily chosen numbers, since they share the same parity. So, if we restrict our sums to only considering f ( n ) for odd numbers, we essentially replace each X with a Bernoulli random variable i 13 with expectation 1 / 7, giving us an estimate of , good for 5 points. 7 This estimate can be substantially improved if we consider other possible factors, which increases the correlation between f ( n − 1) and f ( n + 1) and thus decreases one’s estimate. The correct value of N is 18215.