Question

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 $g(2020) = \text{the digit sum of } 12_8 = 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.$

Answer

Solution:

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: $N = 13333333333_4 = 4^{10} + (4^{10} - 1) = 2 \cdot 4^{10} - 1 = 2097151.$

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

2020 AIME II Problem 5

Solution:

Problem 5 in Other Years