Using your Head is Permitted

March 2013 solution

Answer: yes, the sequence is finite and 888888 is the largest in it.

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

Prefix-followed-by-D-repeated-(n-k)-times,

where Prefix is some digit string (possibly empty), and n and k are both nonnegative integers, with kn. (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:

  1. It is possible to determine if a number is odd or even.
  2. It is possible to divide an even number by two.
  3. It is possible to calculate x from an odd number 2x+1.
For each of the 9 non-zero digits, let us therefore begin by assuming that the initial number is [D]n, with an unknown n. Given the operations above, it is possible to unravel the binary representation of the original number. After each step, we need to further check whether, if n=k, the resulting number (now being solely the Prefix), satisfies the Hamming weight requirement to complete the whole number to Hamming weight D.

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.

Q.E.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