HMMT 十一月 2025 · 团队赛 · 第 4 题

HMMT November 2025 — Team Round — Problem 4

[35] For positive integers n and k with k > 1, let s ( n ) denote the sum of the digits of n when written k in base k . (For instance, s (2025) = 5 because 2025 = 2210000 .) A positive integer n is a digiroot if 3 3 p s ( n ) = s ( n ). Compute the sum of all digiroots less than 1000. 2 4

解析

[35] For positive integers n and k with k > 1, let s ( n ) denote the sum of the digits of n when written k in base k . (For instance, s (2025) = 5 because 2025 = 2210000 .) A positive integer n is a digiroot if 3 3 p s ( n ) = s ( n ). Compute the sum of all digiroots less than 1000. 2 4 Proposed by: Derek Liu Answer: 3069 2 Solution: Since 4 = 2 , to convert a number from base 4 to base 2, we can convert each base-4 digit into two base-2 digits and concatenate them. The digits 0, 1, 2, and 3 in base 4 correspond to 00 , 2 01 , 10 , and 11 , with base-2 digit sums 0, 1, 1, and 2, respectively. In particular, a digit d in base 4 2 2 2 always has base-2 digit sum between d and 2 d , inclusive. Thus, s ( n ) ≤ s ( n ) ≤ 2 s ( n ). 2 4 2 If n is a digiroot, then s ( n ) | s ( n ), so either s ( n ) = s ( n ) = 1 or 2 s ( n ) = s ( n ) = 4. The former 2 4 2 4 2 4 can only be achieved when n in base 4 has a single 1 as its only nonzero digit, while the latter occurs when n in base 4 has two 2’s as its only nonzero digits. In other words, the digiroots are precisely x x y numbers of the form 4 or 2 · 4 + 2 · 4 for nonnegative integers x > y . The resulting digiroots are less than 1000 if and only if x and y are less than 5, so the answer is 4 4 x − 1 4 4 4 5 X X X X X X 4 − 1 x x y x x x 4 + (2 · 4 + 2 · 4 ) = 4 + 4 2 · 4 = 9 4 = 9 = 3069 . 3 x =0 x =0 y =0 x =0 x =0 x =0