Question

对每个正整数 $n$ ，令 $f(n)$ 为 $n$ 以四为底表示时的各位数字之和，令 $g(n)$ 为 $f(n)$ 以八为底表示时的各位数字之和。例如， $f(2020) = f(133210_4) = 10$ $= 12_8$ ，而 $12_8$ 的各位数字之和为 $3$ ，所以 $g(2020) = 3$ 。令 $N$ 为使得 $g(n)$ 以十六为底的表示不能只用数字 $0$ 到 $9$ 表示的最小 $n$ 。求 $N$ 除以 $1000$ 的余数。

For each positive integer $n,$ let $f(n)$ be the sum of the digits in the base-four representation of $n$ and let $g(n)$ be the sum of the digits in the base-eight representation of $f(n).$ For example, $f(2020) = f(133210_4) = 10$ $= 12_8,$ and the digit sum of $12_8$ is $3,$ so $g(2020) = 3.$ Let $N$ be the least value of $n$ such that the base-sixteen representation of $g(n)$ cannot be expressed using only the digits $0$ through $9.$ Find the remainder when $N$ is divided by $1000.$

答案

答案：151

知识点：进制数字逆推法

难度评级：2450

解答：

$g(n)$ 以十六为底的表示需要使用超过 $9$ 的数字，当且仅当 $g(n) \ge 10$ 。所以我们需要 $f(n)$ 以八为底的数字和至少为 $10$ 。按顺序检查数值，所有小于 $31$ 的数以八为底的数字和都至多为 $9$ ，而 $31 = 37_8$ 的数字和为 $10$ 。由于达到给定以四为底数字和的最小 $n$ 随该数字和增大而增大，我们要找满足 $f(n) = 31$ 的最小 $n$ 。

一个以四为底的数字至多为 $3$ ，所以数字和为 $31$ 至少需要 $11$ 位；最小的 $11$ 位选择是首位为 $1$ ，后面跟十个 $3$ ： $\begin{aligned} N &= 13333333333_4 \\ &= 4^{10} + (4^{10} - 1) \\ &= 2 \cdot 4^{10} - 1 = 2097151. \end{aligned}$

$N = 2097151$ 除以 $1000$ 的余数是 $151$ 。

The base-sixteen representation of $g(n)$ needs a digit beyond $9$ exactly when $g(n) \ge 10.$ So we need the base-eight digit sum of $f(n)$ to be at least $10.$ Checking values in order, every number less than $31$ has base-eight digit sum at most $9,$ while $31 = 37_8$ has digit sum $10.$ Since the least $n$ achieving a given base-four digit sum increases with that sum, we want the least $n$ with $f(n) = 31.$

A base-four digit is at most $3,$ so a digit sum of $31$ requires at least $11$ digits, and the smallest $11$ -digit choice is a leading $1$ followed by ten $3$ s: $\begin{aligned} N &= 13333333333_4 \\ &= 4^{10} + (4^{10} - 1) \\ &= 2 \cdot 4^{10} - 1 = 2097151. \end{aligned}$

The remainder when $N = 2097151$ is divided by $1000$ is $151.$

2020 AIME II 第 5 题

答案：151

难度评级：2450

解答：

其他年份的第 5 题