# Multiple of 3 in any numeric base

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.

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

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

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.

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