Define the sequence of decimal integers an as follows: a1 = 0; a2 = 1; an+2 is obtained by writing the digits of an+1 immediately followed by those of an. When is an a multiple of 11?
Answer: n = 1 (mod 6).
Recall that if n = dmdm-1...d1d0, where the di are decimal digits, then the residue of n mod 11 is f(n) = (d0 + d2 + ... ) - (d1 + d3 + ... ). A trivial induction shows that an has an odd number of digits unless n is a multiple of 3. Hence f(an) = -f(an-1) + f(an-2) unless n = 2 (mod 3) when f(an) = f(an-1) + f(an-2). Another simple induction shows that f(an) = 1 for n = 0, 2, 5 (mod 6), -1 for n = 3 (mod 6), 2 for n = 4 (mod 6), and 0 for n = 1 (mod 6).
© John Scholes
12 Dec 1998