3
$\begingroup$

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.

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

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$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.