HMMT 二月 2020 · ALGNT 赛 · 第 4 题

HMMT February 2020 — ALGNT Round — Problem 4

For positive integers n and k , let f ( n, k ) be the number of distinct prime divisors of n that are at least k . For example, f (90 , 3) = 2, since the only prime factors of 90 that are at least 3 are 3 and 5. Find the closest integer to ∞ ∞ ∑ ∑ f ( n, k ) . n + k − 7 3 n =1 k =1

解析

For positive integers n and k , let f ( n, k ) be the number of distinct prime divisors of n that are at least k . For example, f (90 , 3) = 2, since the only prime factors of 90 that are at least 3 are 3 and 5. Find the closest integer to ∞ ∞ ∑ ∑ f ( n, k ) . n + k − 7 3 n =1 k =1 Proposed by: Daniel Zhu Answer: 167 Solution: A prime p is counted in f ( n, k ) if p | n and k ≤ p . Thus, for a given prime p , the total contribution from p in the sum is p ∞ 7 − p ∑ ∑ ∑ 1 1 3 7 7 3 = 3 = . pm + k i 3 3 2 m =1 i ≥ p +1 k =1 Therefore, if we consider p ∈ { 2 , 3 , 5 , 7 , . . . } we get ∞ ∞ 5 4 2 0 ∑ ∑ f ( n, k ) 3 3 3 3 = + + + + ε = 167 + ε, n + k − 7 3 2 2 2 2 n =1 k =1 ∑ 7 − i ∞ 3 1 1 where ε < = . The closest integer to the sum is 167. i =11 2 108 2