# Using your Head is Permitted

## June 2012 solution

Every base *b* has a finite number of "lucky" numbers.
For *b*=2, all lucky numbers must be of the form 11...11_{TWO}.
This gives the numbers 1_{TWO}, 11_{TWO} and 111_{TWO},
but any other length has 1111_{TWO} as a substring, which is composite:
1111_{TWO}=11_{TWO}*101_{TWO}.

For *b*>2, we will show that any string of 2*b*-2 digits will have
a substring of length at least 2 that is a multiple of *b*-1. Because
*b*-1 is an integer greater than 1 and because it is a single digit in
length, the found substring is a non-trivial multiple, making it composite.

Specifically, consider all the even-length prefixes of the string, modulo
*b*-1. If any of these equals zero, the prefix divides *b*-1. If not,
then there are at least two prefixes that are congruent modulo *b*-1.
Consider now the infix that is their string difference (the substring that
begins where the shorter prefix ends and ends where the longer prefix ends).
Because *b* is congruent to 1 modulo *b*-1, the substring's value,
modulo *b*-1, is congruent to the difference between the values of the
two prefixes modulo *b*-1, which makes it 0 (mod *b*-1), so it
divides by this value.

Clearly, this bound is not tight. I thank Radu-Alexandru Todor for some
ingenious suggestions for significantly better bounds. The best possible bound
is unlikely to have a good representation.

Back to riddle

Back to main page