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...11TWO. This gives the numbers 1TWO, 11TWO and 111TWO, but any other length has 1111TWO as a substring, which is composite: 1111TWO=11TWO*101TWO.

For b>2, we will show that any string of 2b-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