# Solution: Special Numbers

Part 1: Prove that there cannot exist a sequence of 14 consecutive special numbers: Consider a special number x that ends in 3 (that is, 3 is the least-significant digit). x must be divisible by three, because it's special and contains a 3 as one of its nonzero digits. As with any number x divisible by three, x+3, x+6, x+9, ... are all also divisible by three, and so are x-3, x-6, x-9, ...

x+10 and x-10 cannot be divisible by 3, but they also contain a 3 (the last digit), and are therefore not special. In other words, a series of 10 or more consecutive special numbers can contain at most one that ends in 3.

The same argument applies to x ending in 4,6,7,8, and 9 (but not to 0, 1 and 2). So a series of special numbers can end in 0,1,2,3,4,5,6,7,8,9,0,1,2 (thirteen numbers), but fourteen is impossible, because such a series would have to contain x ending in 3 (or 4, or 6, or 7,8, or 9) and also x+10.

Part 2: Find a sequence of 13 consecutive special numbers: The obvious answer is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 except that zero is not special (the puzzle defines zero as nonspecial).

We're looking for a sequence of thirteen numbers that end in the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2 such that all are special.

Let's name the first number in the list X. We know that X is a special number that ends in zero, and X+1, X+2, ..., X+12 are all special, too.

Now, X is some (possibly large) number, and it ends in 0. It cannot contain the digit 2. If it did, X+1 would also contain 2, but X+1 ends in 1, and is therefore odd and not divisible by 2 (and therefore not special). In fact, following the same reasoning, it cannot contain any digit 2-9. In can however, contain only the digits zero and one. In addition to this, it must not only end in a zero, but actually end in two zeros, because if the second-to-last digit in X was a 1, then the second-to-last digit in X+11 would be 2, and X+11 would be an odd number that contains a 2, and therefore not special.

Following similar reasoning, X must be divisible by two. This is because X+2 will end in a 2, and since X+2 must be special, it must be divisible by 2, and so that number minus 2 must also be divisible by 2. This reasoning applies to all digits. X must be divisible by 7, because X+7 must be divisible by 7 (since it must be special and it will contain a 7 as the last digit). So, X must contain only zero and ones, end in two zeros, and be divisible by all digits. (You'll see that we get X plus 10, 11, and 12 for "free", because X plus ten and eleven result in numbers that contain only zeros and ones, all of which are special, and X+12 contains only zeros and ones except for the final number 2, which doesn't hurt; all numbers ending in 2 are divisible by 2).

Now all we need is a number, X, containing only zeros and ones, ending in two zeros and divisible by all digits. No problem.

• A number is divisible by 2 if the number ends in 0 or an even number.
• A number is divisible by 3 if the sum of the digits is divisible by three.
• A number is divisible by 4 if the number can be divided by two twice.
• A number is divisible by 5 if the number ends in a zero or a five.
• A number is divisible by 6 if the number is divisible by both 2 and 3.
• A number is divisible by 7 if it is. We'll have to actually do the division.
• A number is divisible by 8 if the number can be divided by two thrice.
• A number is divisible by 9 if the sum of the digits is divisible by nine.

There are ways to "construct" a number that is divisible by every digit by supplying it with the properties above, although the digit 7 is more difficult. Let's define another number, S, which contains only zeros and ones. If the number of ones sums to a multiple of nine, S is divisible by nine. If it doesn't, I can multiply S by 10N (where N is the number of digits in S) and add S. This produces a new number, S', which is written as SS (that is, the sequence of digits in S written twice). S' is still divisible by S (and therefore everything S was divisible by), because only integer multiplication and adding S was applied. This operation can be repeated (it will take at most nine such operations), to produce a number whose digits must sum to a multiple of nine. Now, I multiply the resulting number by 1000 (this ensures that it ends in two zeros). It is now divisible by all digits (except maybe 7):

• It's divisible by 2 because it's even.
• It's divisible by 3 because it's divisible by 9.
• It's divisible by 4 because it's divisible by 1000, which is divisible by 4.
• It's divisible by 5 because it ends in zero.
• It's divisible by 6 because it's divisible by 2 and 3.
• It's divisible by 8 because it's divisible by 1000, which is divisible by 8.
• It's divisible by 9 because we made sure of that.

If the original number S happens to be divisible by 7, the result of these operations will too, so it would be good to start with a value for S which is divisible by 7. The smallest number which qualifies is 1001. We can find the number 1001 with a little guess-and-check (it's only the ninth positive integer that contains only zeros and ones). Using 1001, and applying the operations described, results in the number X as 100110011001100110011001100110011001000. The sequence

```100110011001100110011001100110011001000
100110011001100110011001100110011001001
100110011001100110011001100110011001002
100110011001100110011001100110011001003
100110011001100110011001100110011001004
100110011001100110011001100110011001005
100110011001100110011001100110011001006
100110011001100110011001100110011001007
100110011001100110011001100110011001008
100110011001100110011001100110011001009
100110011001100110011001100110011001010
100110011001100110011001100110011001011
100110011001100110011001100110011001012
```
is a sequence of 13 consecutive special numbers. Of course, there are sequences of 13 consecutive numbers that contain smaller numbers. (Okay, perhaps it is interesting to find the smallest, but this puzzle doesn't ask for that). It would be nice to have a more direct method for finding an integer containing only zeros and ones that is divisible by 7 (although I doubt there is a simple one).

Back