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.
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.
0 Comments:
Post a Comment
<< Home