# 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 *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 possible to determine if a number is odd or even.
- It is possible to divide an even number by two.
- It is possible to calculate
*x* from an odd number 2*x*+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