HMMT 二月 2020 · 冲刺赛 · 第 14 题

HMMT February 2020 — Guts Round — Problem 14

[8] Let ϕ ( n ) denote the number of positive integers less than or equal to n which are relatively prime to 2 n n . Let S be the set of positive integers n such that is an integer. Compute the sum ϕ ( n ) ∑ 1 . n n ∈ S

解析

[8] Let ϕ ( n ) denote the number of positive integers less than or equal to n which are relatively prime 2 n to n . Let S be the set of positive integers n such that is an integer. Compute the sum ϕ ( n ) ∑ 1 . n n ∈ S Proposed by: Joseph Heerens, James Lin 10 Answer: 3 Solution: Let T be the set of prime factors of n . Then n ∏ 2 n p = 2 . φ ( n ) p − 1 p ∈ T We can check that this is an integer for the following possible sets: ∅ , { 2 } , { 3 } , { 2 , 3 } , { 2 , 5 } , { 2 , 3 , 7 } . For each set T , the sum of the reciprocals of the positive integers having that set of prime factors is ( ) ∞ ∏ ∑ ∏ 1 1 = . m p p − 1 m =1 p ∈ T p ∈ T Therefore the desired sum is 1 1 1 1 10 1 + 1 + + + + = . 2 2 4 12 3