We begin by proving finiteness:
The numbers considered here are of the form D-repeated-n-times, where D is some digit and n is a natural. We will denote these [D]n. Let us consider these as part of the larger set of numbers that can be written as
where Prefix is some digit string (possibly empty), and n and k are both nonnegative integers, with k≤n. (We shall see shortly where the separation into n and k helps. For the moment, k is redundant.)
The interesting thing about this notation is that we can perform all of the following operations on a number given in this form, and the result would still belong to the set, and would still be representable using the same n, even when n is not known, and our assumption is only n>k:
It is not possible to continue this process without repeatedly reaching odd numbers and having to subtract one. The reason for this is that the parity of the number is the parity of D, so after at most 3 division-by-2 operations, there must come a subtract-by-1. (The worst case is D=8.)
Therefore, after a finite number of steps, we will already have subtracted-by-1 more than D times, so no completion of Prefix will possibly be able to "complete" to a binary Hamming weight of D.
By following the steps of the algorithm, it is easy to verify that 888888 is, indeed, the largest in the sequence.
Incidentally, this same argument works just as well to prove the finiteness of the corresponding sequence when working in any even base of representation, not just decimal. For odd bases of representation the argument is more complex.
Back to riddle
Back to main page