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 nn . Let S be the set of positive integers n such that is an integer. Compute the sumϕ ( n )
∑
.1
n ∈ Sn
解析
英文解析
- [8] Let ϕ ( n ) denote the number of positive integers less than or equal to n which are relatively prime
2 nto n . Let S be the set of positive integers n such that is an integer. Compute the sumϕ ( n )
∑
.1
n ∈ Sn
Proposed by: Joseph Heerens, James Lin
Answer:10
Solution: Let T be the set of prime factors of n . Then 3
∏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 = .
p p − 1 mm =1
p ∈ T p ∈ T
Therefore the desired sum is
1 1 1 1 10
1 + 1 + + + + = .
2 2 4 12 3