PUMaC 2022 · 团队赛 · 第 13 题

13. Of all functions h : Z → Z , choose one satisfying h ( ab ) = ah ( b ) + bh ( a ) for all a, b ∈ Z

0 ≥ 0 > 0 and h ( p ) = p for all prime numbers p . Find the sum of all positive integers n ≤ 100 such that h ( n ) = 4 n . Proposed by Sunay Joshi Answer: 729 Setting a = b = 1 into the functional equation, we find h (1) = 0 ̸ = 4 · 1. Thus, we may restrict our attention to n > 1. Q P k k e i We now show that if n = p > 1, then h ( n ) = ( e ) n . i i =1 i i =1 To see this, we proceed by induction on n > 1. The base case, n = 2, is evident. Suppose the result holds for all numbers less than n ; we show the result for n . If n is prime, then h ( n ) = n Q k e i by assumption, as desired. Otherwise, we may write the prime factorization n = p , i =1 i where k > 1 and e > 1 for all i . In this case, we may set a = p , b = n/p into the functional i 1 1 equation to find n n h ( n ) = p h + h ( p ) 1 1 p p 1 1 n As 1 < < n by assumption, we may apply the inductive hypothesis to find p 1 k k k X X X n n h ( n ) = p · e − 1 + · p = e − 1 n + n = e n, 1 i 1 i i p p 1 1 i =1 i =1 i =1 completing the induction. Q k e i To solve h ( n ) = 4 n for n = p , it follows that we must find all 2 ≤ n ≤ 100 for which i =1 i P k 4 3 2 2 2 e = 4. These correspond to n with the prime factorizations { p , p q, p q , p qr, pqrs } . i i =1 Considering each of these cases in turn quickly yields the list 4 4 3 3 3 3 3 2 2 2 2 2 2 2 n ∈ { 2 , 3 , 2 · 3 , 2 · 5 , 2 · 7 , 2 · 11 , 3 · 2 , 2 · 3 , 2 · 5 , 2 · 3 · 5 , 2 · 3 · 7 , 3 · 2 · 5 } = { 16 , 81 , 24 , 40 , 56 , 88 , 54 , 36 , 100 , 60 , 84 , 90 } , with sum 729. P h ( n ) Remark: in number theory, the function = e is denoted Ω( n ), and it counts the i i n number of prime factors of n with multiplicity. Numbers with Ω( n ) = k are called k -almost primes.