PUMaC 2019 · 数论（A 组） · 第 2 题

PUMaC 2019 — Number Theory (Division A) — Problem 2

Let f be a function over the natural numbers so that (a) f (1) = 1 e e 1 k (b) If n = p ...p where p , · · · , p are distinct primes, and e , · · · e are non-negative inte- 1 k 1 k 1 k e + .. + e 1 k gers, then f ( n ) = ( − 1) . 2019 ∑ ∑ Find f ( d ). i =1 d | i

解析

If n = p ...p where p , · · · , p are distinct primes, and e , · · · e are non-negative integers, 1 k 1 k 1 k e + .. + e 1 k then f ( n ) = ( − 1) . ∑ ∑ 2019 Find f ( d ). i =1 d | i Proposed by: Marko Medvedev Answer: 44 x +1 k ∑ f ( p ) − 1 k Since the function is completely multiplicative, f ( d ) is given by product of d | i f ( p ) − 1 k which is 0 if x is odd and 1 if x is even (recall that f ( p ) = − 1 for all primes p ). Therefore k k the required sum evaluates to the number of squares less than 2019, which is 44.