HMMT 十一月 2020 · 冲刺赛 · 第 21 题

HMMT November 2020 — Guts Round — Problem 21

[11] Let f ( n ) be the number of distinct prime divisors of n less than 6. Compute 2020 ∑ 2 f ( n ) . n =1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMO 2020, November 14–21, 2020 — GUTS ROUND Organization Team Team ID#

解析

[11] Let f ( n ) be the number of distinct prime divisors of n less than 6. Compute 2020 ∑ 2 f ( n ) . n =1 Proposed by: Milan Haiman Answer: 3431 Solution: Define { 1 a | n 1 = a | n 0 otherwise Then 2 2 f ( n ) = ( 1 + 1 + 1 ) 2 | n 3 | n 5 | n = 1 + 1 + 1 + 2( 1 1 + 1 1 + 1 1 ) 2 | n 3 | n 5 | n 2 | n 3 | n 2 | n 5 | n 3 | n 5 | n = 1 + 1 + 1 + 2( 1 + 1 + 1 ) . 2 | n 3 | n 5 | n 6 | n 10 | n 15 | n 2 So summing f ( n ) over integers 1 ≤ n ≤ 2020 is the same as summing 1 for each time n is divisible by 2, 3, or 5, and additionally summing 2 for each time n is divisible by 6, 10, or 15. ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ (⌊ ⌋ ⌊ ⌋ ⌊ ⌋) 2020 ∑ 2020 2020 2020 2020 2020 2020 2 f ( n ) = + + + 2 + + 2 3 5 6 10 15 n =1 = 1010 + 673 + 404 + 2(336 + 202 + 134) = 3431 .