PUMaC 2022 · 数论（A 组） · 第 8 题
PUMaC 2022 — Number Theory (Division A) — Problem 8
题目详情
- For n ≥ 2, let ω ( n ) denote the number of distinct prime factors of n . We set ω (1) = 0. Compute the absolute value of 160 j k X 160 ω ( n ) ( − 1) . n n =1 Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 1
解析
- For n ≥ 2, let ω ( n ) denote the number of distinct prime factors of n . We set ω (1) = 0. Compute the absolute value of 160 j k X 160 ω ( n ) ( − 1) . n n =1 Proposed by Julian Shah Answer: 22 160 ⌊ ⌋ counts the number of multiples of n less than or equal to 160. Instead of summing over n multiples of integers less than 160, we can sum over divisors of integers less than 160: 160 160 j k X X X 160 Ω( n ) Ω( d ) ( − 1) = ( − 1) n n =1 n =1 d | n P Ω( n ) Note that since f ( n ) = ( − 1) is multiplicative, the function g ( n ) = f ( n ) is also d | n k multiplicative. We can see that g ( p ) = − ( k − 1) for any prime p ; in particular, g ( p ) = 0. Thus g vanishes on any n that has a prime divisor with exponent 1, and we can ignore all P 160 such integers in computing the sum g ( n ). The integers from 1 to 160 that have no prime n =1 divisor of exponent 1 are generated multiplicatively by: the prime powers { 4 , 8 , 16 , 32 , 64 , 128 } , { 9 , 27 , 81 } , { 25 , 125 } , { 49 } , and { 121 } . We see that most of these generators can’t be multiplied by anything else without exceeding 160. Thus we are then left to do casework on the generators { 4 , 8 , 16 } , { 9 , 27 } , and { 25 } , which is much simpler. This yields the additional values of 4 · 9 = 36, 4 · 27 = 108, 4 · 25 = 100, 8 · 9 = 72, 16 · 9 = 144. We must also include n = 1 in our sum. Summing, we find an value of 1 + ( − 1 − 2 − 3 − 4 − 5 − 6) + ( − 1 − 2 − 3) + ( − 1 − 2) + ( − 1) + ( − 1) + (1 + 2 + 1 + 2 + 3) = − 22, so our answer is 22. 4