PUMaC 2021 · 团队赛 · 第 13 题
PUMaC 2021 — Team Round — Problem 13
题目详情
- Given a positive integer n with prime factorization p p · · · p , we define f ( n ) to be p e . i i 1 2 k i =1 In other words, f ( n ) is the sum of the prime divisors of n , counted with multiplicities. Let M be the largest odd integer such that f ( M ) = 2023 , and m the smallest odd integer so that e e e M 1 2 l f ( m ) = 2023 . Suppose that equals p p · · · p , where the e are all nonzero integers and i 1 2 m l l P the p are primes. Find | ( p + e ) | . i i i i =1
解析
- Given a positive integer n with prime factorization p p · · · p , we define f ( n ) to be p e . i i 1 2 k i =1 In other words, f ( n ) is the sum of the prime divisors of n , counted with multiplicities. Let M be the largest odd integer such that f ( M ) = 2023 , and m the smallest odd integer so that e e e M 1 2 l f ( m ) = 2023 . Suppose that equals p p · · · p , where the e are all nonzero integers and i 1 2 l m l P the p are primes. Find | ( p + e ) | . i i i i =1 Proposed by: Frank Lu Answer: 2695 We first find what M is. To do this, we first notice that every positive odd integer other than 1 can be written in the form 3 a + 5 b + 7 c, where a, b, c are non-negative integers. To do this, observe that every positive odd integer other than 1 can be written in either the form 6 k + 3 , 6 k + 5 , or 6 k + 7 , where k is a nonnegative integer. It’s not hard to see that, with these forms, we can find nonnegative integers a, b, c for each of these cases. 6 From here, suppose that n ∈ S and is odd. Then, if n is divisible by any prime p that isn’t one of 3 , 5 , 7 , then by the above, since n is odd, p is odd, so we can write p = 3 a + 5 b + 7 c, a b c n 3 5 7 where a, b, c are nonnegative integers. Replacing n with yields another integer that lies p a b c a b c a + b + c in S. But notice that 3 5 7 > p. To see this, notice that 3 5 7 ≥ 3 > 7( a + b + c ) ≥ p, n if a + b + c ≥ 3 . We can verify that 3 > 7 n for n ≥ 3 , by induction. As for a + b + c = 1 , 2 , observe that these are impossible, since p is odd and not one of 3 , 5 , 7 . But this means that M is only divisible by primes in { 3 , 5 , 7 } . 2 2 3 3 Furthermore, if n is divisible by 7 , we can replace 7 with 3 · 5 , and if n is divisible by 5 , we 5 can replace it with 3 . Finally, if n is divisible by 5 · 7 , then we can replace this product with 4