PUMaC 2023 · 团队赛 · 第 5 题

PUMaC 2023 — Team Round — Problem 5

Let S denote the set of all positive integers whose prime factors are elements of { 2 , 3 , 5 , 7 , 11 } . (We include 1 in the set S .) If X φ ( q ) 2 q q ∈ S a can be written as for relatively prime positive integers a and b , find a + b . (Here φ denotes b Euler’s totient function.)

解析

Let S denote the set of all positive integers whose prime factors are elements of { 2 , 3 , 5 , 7 , 11 } . (We include 1 in the set S .) If X φ ( q ) 2 q q ∈ S 2 can be written as a/b for relatively prime positive integers a and b , find a + b . (Here φ denotes Euler’s totient function.) Proposed by Sunay Joshi Answer: 1537 Since φ is multiplicative, the desired sum equals k Y X φ ( p ) k 2 ( p ) k ≥ 0 p ∈{ 2 , 3 , 5 , 7 , 11 } k k − 1 0 We now consider the inner sum. Note that φ ( p ) = p ( p − 1) for k ≥ 1, while φ ( p ) = 1. Hence the sum reduces to X p − 1 p − 1 1 p + 1 1 + = 1 + · = k +1 2 p p 1 − 1 /p p k ≥ 1 Therefore the desired sum equals 3 4 6 8 12 1152 · · · · = , 2 3 5 7 11 385 and our answer is 1537.