HMMT 十一月 2014 · 冲刺赛 · 第 34 题
HMMT November 2014 — Guts Round — Problem 34
题目详情
- [ 20 ] Let M denote the number of positive integers which divide 2014!, and let N be the integer closest to ln( M ). Estimate the value of N . If your answer is a positive integer A , your score on this problem ⌊ ⌋ 1 will be the larger of 0 and 20 − | A − N | . Otherwise, your score will be zero. 8
解析
- [ 20 ] Let M denote the number of positive integers which divide 2014!, and let N be the integer closest to ln( M ). Estimate the value of N . If your answer is a positive integer A , your score on this problem ⌊ ⌋ 1 will be the larger of 0 and 20 − | A − N | . Otherwise, your score will be zero. 8 Answer: 439 Combining Legendre’s Formula and the standard prime approximations, the answer is ( ) ∏ 2014 − s (2014) p 1 + p − 1 p where s ( n ) denotes the sum of the base p -digits of n . p Estimate ln 1000 ≈ 8, and ln 2014 ≈ 9. Using the Prime Number Theorem or otherwise, one might estimate about 150 primes less than 1007 and 100 primes between 1008 and 2014. Each prime between 1008 and 2014 contributes exactly ln 2. For the other 150 primes we estimate ln 2014 /p as their ∑ contribution, which gives (ln 2014 − ln p ). Estimating the average ln p for p < 1000 to be p< 1000 ln 1000 − 1 ≈ 7 (i.e. an average prime less than 1000 might be around 1000 /e ), this becomes 150 · 2 = 300. So these wildly vague estimates give 300 + 150 ln 2 ≈ 400, which is not far from the actual answer. The following program in Common Lisp then gives the precise answer of 438 . 50943. ;;;; First, generate a list of all the primes (defconstant +MAXP+ 2500) (defun is-prime (p) (loop for k from 2 to (isqrt p) never (zerop (mod p k)))) (defparameter primes (loop for p from 2 to +MAXP+ if (is-prime p) collect p)) ;;;; Define NT functions Guts Round (defconstant +MAXDIGITS+ 15) (defun base-p-digit (p i n) (mod (truncate n (expt p i)) p)) (defun sum-base-p-digit (p n) (loop for i from 0 to +MAXDIGITS+ sum (base-p-digit p i n))) (defun vp-n-factorial (p n) (/ (- n (sum-base-p-digit p n)) (1- p))) ;;;; Compute product (princ (loop for p in primes sum (log (1+ (vp-n-factorial p 2014)))))