Problem:
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(133210four )=10=12eight , and g(2020)= the digit sum of 12eight =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.
Solution:
We want g(n)≥1016=1610. Since g(n) is the digit sum of f(n) written in base 8, we seek the smallest f(n) such that its base-8 digit sum is at least 10.
Try f(n)=378=3⋅8+7=31, which has digit sum 3+7=10. This is the smallest such value. So we want the least n for which f(n)=31 — that is, the base-4 digit sum of n is 31.
To minimize n, maximize the use of digit 3 in base-4. Using ten 3's gives 3⋅10=30, which is too small. Use one more digit: 3⋅10+1=31.
So the minimal base-4 number with digit sum 31 is 133333333334 (one 1 followed by ten 3's).
Convert to base-10:
n=1⋅410+3⋅(49+48+⋯+40)
Use geometric sum:
3⋅(3410−1)=410−1
So:
n=410+(410−1)=2⋅410−1
Now compute 2⋅410−1(mod1000).
Note that 410=220=1048576, so 2⋅410=2097152 and 2097152(mod1000)=152.
So, N = 2 \cdot 4^{10} - 1 \equiv 152 - 1 = \boxed{151} \pmod
The problems on this page are the property of the MAA's American Mathematics Competitions