TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Wednesday, May 17, 2006

A Sequence Puzzle

The following problem was contributed by B. Sairam.

There is a series which goes like this

T(1) = 1
T(2) = 2
T(k) = T(k-1) + SumOfDigitsOf ( T(k-1) ). For instance, if T(p) = 129 then
T(p+1) = 129+1+2+9

Question: Then does the number 123456789 occur in this series?

Spoiler Warning: Solution below!

[Additional questions: How fast does the function digitsum(N) grow as a function of N? How fast does the therm T(N) in the above series grow with N?]

-----------












-----------
Of course, it is easy to check programmatically that 123456789 does not occur in the series. A non-brute-force argument follows....
-----------










Every number N and digitsum(N) both have the same value modulo 3.

When a number that equals 1 (modulo 3) is added to its own digitsum, the value of the sum (modulo 3) will be 2.

When a number that equals 2 (modulo 3) is added to its own digitsum, the value of the sum (modulo 3) will be 1.

The series begins with 1, which equals 1 (modulo 3). the next will be 2, which equals 2 (modulo 3). The next number is 4 which equals 1 (modulo 3) the next number will equal 2 (modulo 3) and so on...

Thus,the series consists alternately of numbers equaling 1 and 2 modulo 3. But the given number equals 0 modulo 3 (since it can be easily checked it is divisible by 3). so, it cannot be in the series. QED.