# A question about “binary numbers in arbitrary bases”

Here's a problem that I had come up with some time ago:

Let a "binary number in base $n$" refer to a natural number whose representation in base $n$ consists of only $0$'s and $1$'s. Prove that every natural number can be expressed as the sum of a binary number in base $3$, a binary number in base $4$, and a binary number in base $5$.

I eventually managed to prove it (which will for the time being be left as an exercise to the reader as I seem to have deleted the only copy of it that I had). But the discoveries in that proof eventually gave rise to another question:

Given some collection of numbers $a_1, a_2, a_3, \ldots, a_n\ (a_k \ge 2)$ so that $\displaystyle \sum_{k=1}^n \frac{1}{a_k-1} \geq 1$, every natural number can be expressed as the sum of binary numbers $b_1, b_2, b_3, \ldots, b_n$ so that for all $1 \le k \le n$, $b_k$ is in base $a_k$.

Is this true? If so, can you prove it?

-
+1, if only for the parenthetical remark! (Actually, it looks like an interesting question.) –  Brian M. Scott Mar 19 '13 at 3:47
You can't make 4 by adding three elements chosen (with replacement) from $\{ 0, 1 \}$, and every other binary number in base 5 is bigger than 4. Did you mean to allow negative numbers in the sum? –  Hurkyl Mar 19 '13 at 3:51
@Hurkyl 4 = 10 in base 4 + 0 in base 3 + 0 in base 5. –  Joe Z. Mar 19 '13 at 3:52
One number per base. Perhaps that was confusing. –  Joe Z. Mar 19 '13 at 3:52

Yes, I think this should follow easily from two very simple lemmas:

Lemma 1: If $S = ( a_1 \le a_2 \le a_3 \le \cdots)$ is a multiset of positive integers, then every natural number can be represented as a sum of distinct elements from $S$ iff for all $k\ge 0$, $$\tag{*}\sum_{i=1}^k {a_i} \ge a_{k+1}-1.$$ Equivalently: for each $m$, the elements of $S$ not exceeding $m$ sum to at least $m$.

Proof. One direction is obvious: if $\sum_{i=1}^k {a_i} < a_{k+1}-1$ for some $k$ then there is no way to represent $a_{k+1}-1$ as a sum of elements of $S$.

In the converse direction, we show by induction that if $S$ satisfies (*), then every nonnegative integer up to $\sum_{i=1}^n a_i$ can be represented as a sum of terms from $S_n := (a_1, a_2, \ldots, a_n)$. The base case $n=1$ is easy because (*) with $k=0$ implies that $a_1 = 1$.

For the induction step, suppose $S_n$ represents every number up to $M$ where $M \ge a_{n+1}-1$. Then it's easy to see that $S_{n+1}$ represents every $0 \le x \le M+a_{n+1}$: if $0 \le x \le M$ this is obvious, while if $x \ge M+1 \ge a_{n+1}$, then $x-a_{n+1}$ is a nonnegative integer not exceeding $M$, which can be represented by $S_n$. Now just add $a_{n+1}$.

This proves the first equivalence. We now observe that (*) is equivalent to the statement that $\sum_{x \in S, x \le m} x \ge m$ for each $m$. If (*) holds then for any $m \in \mathbb N$, let $k$ be the largest integer such that $a_k \le m$. Then the sum of all elements up to $m$ is precisely $\sum_{i=1}^k a_k \ge a_{k+1} - 1 > m-1$, making it at least $m$.

In the other direction, (*) is vacuously true whenever $a_k = a_{k+1}$, so assume that $a_k < a_{k+1}$. Now choose $m=a_{k+1}-1 \ge a_k$, and apply the property that all elements up to $m$ sum to at least $m$.

Lemma 2: Let $b \ge 2$ and $n \in \mathbb N$. The sum of all $b^i$ not exceeding $n$ is at least $\frac{n}{b-1}$.

Proof. This one is very easy. If $r$ is the largest integer such that $b^r \le n$, then $n < b^{r+1}$, hence $n \le b^{r+1}-1 = (b-1)(1 + b + \cdots + b^r)$.

Finally, combining these two lemmas gives the claim in the question: let $S$ be the multiset of all nonnegative powers of all $a_k$. For each $m \in \mathbb N$, the sum of all elements of $S$ up to $m$ is at least $\sum_k \frac{m}{a_k-1} \ge m$.

-
I thought that too, but realized I had no actual proof. –  Joe Z. Mar 19 '13 at 13:07
@JoeZeng Do you recall any specific gaps in the argument? –  Erick Wong Mar 19 '13 at 17:25
Unfortunately not. I was thinking, what happens when there is a specific gap in the available results? Does that ever happen? If the gap was small enough, would it eventually be covered over so that there is a maximum un-representable number? –  Joe Z. Mar 19 '13 at 20:23
@JoeZeng Let me add some details to turn this into a proof (or expose any missing pieces). –  Erick Wong Mar 19 '13 at 21:54
Great! Accepted for that. –  Joe Z. Mar 20 '13 at 0:20