Solution to Problem 111



Congratulations to this week's winner,

Mundia Mubyana

Correct solutions were also submitted by Ray Kremer, David Smith, Further correct solutions came from Thiry Ives, Hy Nguyen, Brian Laughlin, Stephen Smith, Jonathan Lewin, Jens Voss, Ron Welch, Burkart Venzke, Ivan Lisac, Robin J. Rhee, Khann Ngo, Sudipta Das, Philippe Fondanaiche, Nancy Schwarzkopf, Vinko Marinkovic, Michael Lynch, Francesc Suñol i Esquirol.

123456789 is not in the sequence.

Several people submitted computer programs which they used to check this by brute force.  For instance, the pairs (n, an) include (3641311, 123456718),  (3641312, 123456755),  (3641312, 123456793).

A more subtle argument proceeds as follows.  Any integer is congruent to the sum of its digits modulo 9 -- this lies at the root of  "casting out nines".  So if we denote by sn the sum of the digits of an, then

sn º an (mod 9),
sn+1 = sn + an º 2sn (mod 9)
A straightforward induction based on s1 = a1 = 1 gives sn+1 º 2n, for all n.  Now it's easy to check that 2n º 1,2,4,5,7,8 (mod 9) while 123456789 º 0 (mod 9).

You are visitor number 2927 to this page.
Page last updated 2 April 2001.

ã 2001 Alberto L Delgado