# 2017 AIME II Problems/Problem 4

## Problem

Find the number of positive integers less than or equal to $2017$ whose base-three representation contains no digit equal to $0$.

## Solution

### Solution 1

The base- $3$ representation of $2017_{10}$ is $2202201_3$. Because any $7$-digit base- $3$ number that starts with $22$ and has no digit equal to $0$ must be greater than $2017_{10}$, all $7$-digit numbers that have no digit equal to $0$ must start with $21$ or $1$ in base $3$. Of the base- $3$ numbers that have no digit equal to $0$, there are $2^5$ $7$-digit numbers that start with $21$, $2^6$ $7$-digit numbers that start with $1$, $2^6$ $6$-digit numbers, $2^5$ $5$-digit numbers, $2^4$ $4$-digit numbers, $2^3$ $3$-digit numbers, $2^2$ $2$-digit numbers, and $2^1$ $1$-digit numbers. Summing these up, we find that the answer is $2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\boxed{222}$.

### Solution 2

Note that $2017=220221_{3}$, and $2187=3^7=10000000_{3}$. There can be a $1,2,...,7$ digit number less than $2187$, and each digit can either be $1$ or $2$. So $2^1$ one digit numbers and so on up to $2^7$ $7$ digit.

Now we have to subtract out numbers from $2018$ to $2187$

Then either the number must begin $221...$ or $222...$ with four more digits at the end

Using $1$s and $2$s there are $2^4$ options for each so: $2+4+8+16+32+64+128-2*16=256-2-32=\boxed{222}$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 