# Base $5$ representation is the last $k$ digits of its base $2$ representation for some $k$

Compute the largest integer between $1$ and $1000$ whose base $5$ representation consists of the last $k$ digits of its base $2$ representation, for some $k$.

I thought about taking cases based on the number of leading $1$s such a number $n$ has in base $5$. Since $1000 = 13000_5$, there are many possibilities to check using this approach. For example, if the number of leading $1$s is $1$, then \begin{align*}n &= 10_5, 100_5,101_5,1000_5,1010_5,1011_5,1001_5,10000_5,10001_5,10010_5,10011_5,10100_5,10101_5,\\&=10110_5,10111_5.\end{align*}

The number of cases here is $2^0+2^1+2^2+2^3 = 15$. Then we would also have to check if each of these satisfies the requirements.

• Is 1000 in base 5, base 2, or base 10? – Toby Mak Jun 6 '17 at 0:15
• @TobyMak It is in base $10$. – user19405892 Jun 6 '17 at 0:16
• $1000_{10}$ in base $5$ and base $2$ has $k=2$ shared trailing zeroes – Zubin Mukerjee Jun 6 '17 at 0:18
• @ZubinMukerjee looks like the full base 5 representation has to be the last $k$ bits in base 2. – peterwhy Jun 6 '17 at 0:20
• Like thirty-one, then? – Oscar Lanzi Jun 6 '17 at 0:27

If a number $n$ has $k$ digits (quits?) in base $5$, then let $$n = \sum_{i=0}^{k-1} a_i 5^i = a_{k-1} 5^{k-1} + \cdots + a_15 + a_0,$$ where $a_{k-1} > 0$. Since the same digits $a_i$ are used as bits, $a_i \in \{0, 1\}$.

Consider the last $k$ bits in base $2$:

\begin{align*} n &\equiv \sum_{i=0}^{k-1} a_i 2^i \pmod{2^k}\\ \sum_{i=0}^{k-1} a_i 5^i &\equiv \sum_{i=0}^{k-1} a_i 2^i\\ \sum_{i=0}^{k-1} a_i (5^i-2^i)&\equiv 0\\ \end{align*}

For $k=5$, which is the largest possible $k$,

\begin{align*} 609a_4 + 117a_3 + 21a_2 + 3 a_1 &\equiv 0 \pmod {32}\\ a_4 + 21a_3 + 21 a_2 + 3a_1 &\equiv 0 \end{align*} Which does not look possible given that $a_4$ must be $1$.

For $k = 4$,

\begin{align*} 117a_3 + 21a_2 + 3 a_1 &\equiv 0 \pmod {16}\\ 5a_3 + 5 a_2 + 3a_1 &\equiv 0 \end{align*} Which does not look possible given that $a_3$ must be $1$.

For $k = 3$,

\begin{align*} 21a_2 + 3 a_1 &\equiv 0 \pmod {8}\\ 5 a_2 + 3a_1 &\equiv 0 \end{align*}

So $a_2 = a_1 = a_0 = 1$ is a solution (and gives a larger $n$ than setting $a_0 = 0$). The result is

$$n = 5^2+5^1+1 = 111_5 = 31 = 11111_2$$

• Both thirty and thirty-one, maybe? – Oscar Lanzi Jun 6 '17 at 1:16
• @OscarLanzi Both (and also one) are valid, but the question asks for the largest integer between 1 and 1000. – peterwhy Jun 6 '17 at 1:21