Infinite positive integer sequence with distinctive sum of digits

Question

I am looking at this problem. Interestingly most problems on that site has solutions except this one, thus I am asking here.

https://www.komal.hu/feladat?a=feladat&f=A728&l=en

Essentially, for question (a), we are asked to construct an infinite positive integer sequence $\{ a_i \}$ such that $a_{i+1} \leq 2a_i$, and the sums of decimal digits of each item in the integer sequence are distinct. For question (b), we are ask to prove if this is possible for binary digits.

I am not even sure if question (a) is feasible at all.

We will probably want to guarantee that the sum of digits is ascending as well, because otherwise we will run of of numbers eventually. Since if we ever had digit $9$ as the last digit, say $99$, then from 99 to $2*99$, there is no number with sum of digits greater than $18$. But it seems like I will always hit a number with last digit = 9 however I construct my series

Answer 1

Question (a), the decimal case, has been answered in the comments. This answer addresses question (b), the binary case.

Preliminaries

In this answer, the natural numbers $\Bbb N$ are taken to be the strictly positive integers $1,2,3,\dots$

If $n\in\Bbb N$, we use $\ell(n)$ to denote the number of digits in the binary expansion of $n$. So $2^{\ell(n)-1}\le n<2^{\ell(n)}$.

We call a (finite or infinite) sequence $(a_i)=(a_1,a_2,\ldots)$ of natural numbers valid if (i) $a_{i+1}\le 2a_i$ for all $i\in\Bbb N$, and (ii) the number of $1$'s in the binary expansion of $a_i$ is different for each element.

Given a valid sequence $(a_i)$, we can pre-process it in two ways:

1. We can sort the sequence into increasing order. The resulting sequence will also be valid.
2. After sorting, $\ell(a_{i+1})$ must equal $\ell(a_i)$ or $\ell(a_i)+1$ for all $i$. But the number of instances where $\ell(a_{i+1})=\ell(a_i)$ must be finite: $\ell(a_i)$ must always be $\ge i$ (because there are $i$ different $1$-counts among the elements $a_1,\ldots,a_i$), but each such instance decreases the excess $\ell(a_i)-i$ by $1$.

So if we start with an infinite valid sequence $(a_i)$, we can sort it and then discard all elements up to and including the last instance where $\ell(a_{i+1})=\ell(a_i)$; and we end up with an infinite valid sequence with strictly increasing bit lengths. We call this a lengthening sequence.

Theorem

There is no valid infinite sequence.

Proof

Suppose we have an infinite valid sequence $(a_i)$. We may suppose that it is a lengthening sequence, as defined above. Let $Z_n$ be the average number of $0$'s in the binary expansions of the $n$ integers $a_1,\ldots,a_n$, and let $k=\ell(a_1)$ be the number of digits in the binary expansion of $a_1$. Then we will show that

• $Z_n\le k-1$ for all $n$;
• $Z_n\ge k$ for all sufficiently large $n$.

This contradiction establishes the theorem.

Part I

From $\ell(a_{i+1})=\ell(a_i)+1$, we have $\ell(a_i)=k+i-1$ for all $i$. So the total number of binary digits in all the integers $a_1,\ldots,a_n$ is $$C=\sum_{i=1}^n(k+i-1)=(k-1)n+\frac12n(n+1)$$

Of these digits, at least $$D=\sum_{i=1}^n i=\frac12n(n+1)$$ must be $1$'s, because each $a_i$ has a different number of $1$'s.

Therefore at most $C-D=n(k-1)$ of these digits can be $0$. Hence the average number of zeroes $Z_n$ can be at most $k-1$.

Part II

Define the sequence $(x_1,x_2,\ldots)$ of real numbers by $x_i=2^{-(n+k)}a_i$. What we are doing here is mapping the sequence $(a_i)$ of integers, such as $$(1111_2,11100_2,110111_2,1100000_2,10111111_2,\ldots)$$ to the sequence $(x_i)$ of real numbers $$(0.1111_2,0.11100_2,0.110111_2,0.1100000_2,0.10111111_2,\ldots)$$ in the interval $[\frac12,1)$. This sequence is monotonic decreasing, and bounded below, therefore it has an infimum $m$. Let $m_i$ denote the $i$th binary digit after the decimal (binary?) point.

Now, if $(m_i)$ contained only a finite number of $0$'s, it would end in $...0111\ldots$ , which we can replace by $...1000\ldots$ So we can always choose the $m_i$ so that an infinite number of them are $0$. Now choose $M$ such that the number of $0$'s in the sequence $(m_1,\ldots,m_M$) (i.e. the first $M$ binary digits of $m$) is $\ge k+1$.

Because the sequence $x_i$ tends to the limit $m$ from above, there exists $N$ such that $0\le x_i-m<2^{-(N+1)}$ whenever $i\ge N$. So the first $N$ binary digits of $x_i$ and $m$ must be identical. This means that the binary expansion of $x_i$ (and therefore of $a_i$) contains at least $k+1\;$ $0$'s for all $i\ge N$. (Note: this requires the fact that we are dealing with a lengthening sequence! Otherwise $\ell(a_i)$ might be less than $k+i-1$, and we couldn't necessarily count all $0$'s in $x_i$ as $0$'s in $a_i$.) So the average number of $0$'s in the first $(k+1)N$ integers $a_i$ is at least $$\frac{(k+1)\cdot kN}{(k+1)N}=k$$ as claimed. This completes the proof.

---

Further thoughts

1. I feel that this problem shouldn't require the machinery of real analysis! But I couldn't find a combinatoric proof, despite strenuous efforts. Perhaps somebody out there can fill this gap.

2. If $k=4$ we have the maximal-length sequence $$1111_2\\ 11100_2\\ 110111_2\\ 1100000_2\\ 10111111_2\\ 101111100_2\\ 1011110111_2\\ 10111011111_2\\ 101101111111_2\\ 1010111111111_2\\ 10011111111111_2\\ 100000000000000_2$$

This was generated by following the simple rule of always choosing the largest admissible integer as the next element of the sequence; an exhaustive search was also done to prove that this is a maximal lengthening sequence.

But if we follow the same rule in the case $k=5$, we generate a sequence of length $65532$. Exhaustive search is obviously out of the question here; all I can say is, I expect that this sequence is maximal too.