## A very long number

From the 2000 University of Waterloo Cayley Contest:

The leftmost digit of an integer of length 2000 digits is 3. In this integer, any two consecutive digits must be divisible by 17 or 23. The 2000th digit may be either ‘a’ or ‘b’. What is the value of a+b?

It makes sense to begin by listing all the two digit multiples of 17 and 23:

17, 34, 51, 68, 85,

23, 46, 69, 92.

The first digit is 3, so the second digit must be 4, and the third must be 6. Now we have a choice for the fourth digit – 8 or 9.

Suppose we choose 8; then this must be followed by a 5, then a 1, then a 7, then… oh dear, we have no options at all. So in fact the fourth digit must be a 9, the fifth a 2, and the sixth a 3.

But we had a digit 3 at the beginning, so we are just going to cycle through the same logic over and over again, with the pattern ‘34692’ repeating for almost the entire length of the number. I say almost, because after the 399th block of ‘34692’, we will have only five digits left to fill, and so picking 8 instead of 9 wouldn’t be such a disaster: in this case the final five digits would be ‘34685’.

This means the two possible choices for the final digit are 2 and 5, and so a + b = 7.

I think this is a great little problem, well designed and accessible to many.