PUMaC 2022 · 数论（A 组） · 第 5 题
PUMaC 2022 — Number Theory (Division A) — Problem 5
题目详情
- A positive integer ℓ ≥ 2 is called sweet if there exists a positive integer n ≥ 10 such that when the leftmost nonzero decimal digit of n is deleted, the resulting number m satisfies n = mℓ . Let P 1 A S denote the set of all sweet numbers ℓ . If the sum can be written as for relatively ℓ − 1 B ℓ ∈ S prime positive integers A, B , find A + B . √ ( ℓ ) ( ℓ ) 1 ∞ ℓ
解析
- A positive integer ℓ ≥ 2 is called sweet if there exists a positive integer n ≥ 10 such that when the leftmost nonzero decimal digit of n is deleted, the resulting number m satisfies n = mℓ . Let P 1 A S denote the set of all sweet numbers ℓ . If the sum can be written as for relatively ℓ − 1 B ℓ ∈ S prime positive integers A, B , find A + B . Proposed by Sunay Joshi Answer: 71 Let ν ( t ) denote the highest power of the prime p dividing t . We claim that ℓ ≥ 2 is sweet iff: p (i) all prime factors of ℓ − 1 are elements of { 2 , 3 , 5 , 7 } , (ii) ν ( ℓ − 1) ≤ 2, (iii) ν ( ℓ − 1) ≤ 1, 3 7 (iv) 3 · 7 does not divide ℓ − 1, and (v) ℓ − 1 ̸ = 1 , 3 , 7 , 9. To see this, suppose that n = mℓ , k where m is the number obtained by deleting the leftmost digit of n . Write n = 10 a + b , where a ∈ { 1 , . . . , 9 } is the leftmost digit of n , so that m = b . Then n = mℓ is equivalent to k k 10 a + b = ℓb , or ( ℓ − 1) b = 10 a for some k -digit number b . k k The condition ( ℓ − 1) b = 10 a for an arbitrary positive integer b is equivalent to ( ℓ − 1) | 10 a for some a ∈ { 1 , . . . , 9 } , which is equivalent to the first four conditions above. k k If ℓ − 1 ≥ 10, then ( ℓ − 1) b = 10 a for some k -digit number b is equivalent to ( ℓ − 1) | 10 a , k k since the equality forces b to have at most k digits: b ≤ 10 · 9 / 10 < 10 . If ℓ − 1 ∈ { 1 , . . . , 9 } , then in the cases ℓ − 1 ∈ { 1 , 3 , 7 , 9 } , b must have at least k digits. The value of b in each case k k k k 10 3 · 10 7 · 10 9 · 10 is at least , , , and , respectively. 1 3 7 9 Thus ℓ ∈ S iff the five conditions above hold. In terms of prime factorization, ℓ ∈ S iff ℓ − 1 ̸ = x y z w 1 , 3 , 7 , 9 and ℓ − 1 = 2 5 3 7 , where x ≥ 0, y ≥ 0, and ( z, w ) ∈ { (0 , 0) , (0 , 1) , (1 , 0) , (2 , 0) } . Splitting the desired sum into a product over primes, we find X X X 1 1 1 1 1 1 1 1 1 1 = 1 + + + − ( + + + ) , x y 2 ℓ − 1 2 5 3 3 7 1 3 7 9 ℓ ∈ S x ≥ 0 y ≥ 0 where we subtract terms corresponding to the cases ℓ − 1 = 1 , 3 , 7 , 9. By the geometric series 250 100 50 formula, this equals − = . Thus our answer is 50 + 21 = 71. 63 63 21 √ ( ℓ ) ( ℓ ) 1 ∞ ℓ