8
$\begingroup$

Can you find a positive binary number that is a multiple of 3 when it is read in any base from 2 to 10? A binary number contains only digits 0 and 1. For example the binary number "11" is 3 when read in base 2, 4 in base 3, 5 in base 4, ..., 11 in base 10.

$\endgroup$
0

2 Answers 2

14
$\begingroup$

One answer that satisfies the question is

1010100, whose value in base 2 to 10 is 84, 819, 4368, 16275, 47988, 120099, 266304, 538083, and 1010100 respectively. Actually, this number is a multiple of 3 when read in any base ≥ 2.

How I found it:

In order to be a multiple of 3 in base 3/6/9, the last digit must be 0. Now, observe that $$n^2 \equiv 1 \mod 3$$ for any integer $n$ not divisible by 3. Since modulo is additive and multiplicative, $$n^6+n^4+n^2 \equiv 1^3 + 1^2 + 1 \equiv 0 \mod 3$$ and see that the LHS is the number 1010100 evaluated in base $n$.

The smallest possible (strictly positive) answer is

101010

because

it works in multiple-of-3 bases (since the last digit is 0) and $$n^5+n^3+n^1 \equiv n + n + n = 3n \equiv 0 \mod 3$$ for non-multiple-of-3 bases. But dividing by $n$ further doesn't work for multiple-of-3 bases. Mixing even and odd powers does not work either, because $n$ and $1$ modulo 3 cannot cancel each other in all values of $n$.

$\endgroup$
3
  • $\begingroup$ Very well done. You got it! $\endgroup$ Dec 1, 2020 at 7:41
  • 2
    $\begingroup$ oeis.org/A329126 $\endgroup$
    – msh210
    Dec 1, 2020 at 9:11
  • $\begingroup$ that's where I found the idea for this puzzle $\endgroup$ Dec 1, 2020 at 9:30
2
$\begingroup$

As a broader solution approach, consider that any binary number can be expressed in the form

$$ A_2=\sum_{k=1}^m 2^{f_k} $$ where $f_k$ is a strictly increasing sequence of nonnegative integers. [the remainder of the answer is in spoiler boxes, split into sections so that you can see portions of the answer without spoiling the whole thing]

The same digits interpreted in base $N$ will be read as $$ A_N=\sum_{k=1}^m N^{f_k} $$

Now, we need it to be a multiple of 3 in all bases. Therefore, we have $$ 0\equiv\sum_{k=1}^m N^{f_k}\mod 3 $$

and because we are working modulo 3, we only actually care about three cases: $N=3n$, $N=3n+1$, and $N=3n+2$. This gives us three equations: $$ \sum_{k=1}^m 1=m\equiv0 \mod 3 $$ $$ \sum_{k=1}^m 2^{f_k}\equiv0\mod 3 $$ and $$ \sum_{k=1}^m 0^{f_k}\equiv0\mod 3 $$

Now, for the last equation, $0^{f_k}=0$ for $f_k>0$, but $0^0=1$, so we require that $f_1>0$. This is equivalent to saying that the units digit must be zero.

The first equation says that the number of ones must be a multiple of 3. The second equation says that the number in base 2 must be divisible by 3. Alternatively, you can replace the $2$ in the second equation with $(-1)$, and it says that difference between the number of ones in the even places and the number of ones in the odd places must be a multiple of 3 (where the final digit is the 0th digit, and thus even).

Combining these conditions, the conclusion is that there must be a multiple of 3 number of 1s in even digit places, and a multiple of 3 number of 1s in odd digit places.

As noted in Bubbler's great answer, the smallest solution is

101010, which has three ones, all in odd places, with a zero at the end. To put it another way, it's the smallest multiple of 3 with three ones and a zero at the end.

The next solutions are 1010100, 1111110, and 10001010.

$\endgroup$
1
  • $\begingroup$ Thank you Glen. This is a nice way to look at the problem. $\endgroup$ Dec 3, 2020 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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