SEARCH HOME
 Math Central Quandaries & Queries
 Question from Shamik: Question: A sequence of numbers is defined in the following way. B(1) = 1 B(n) = B(n-1) + {Sum of the digits of B(n-1)} for n > 1. B(1) = 1 B(2) = 2 B(3) = 4 B(4) = 8 B(5) = 16 B(6) = 23 B(7) = 28 B(8) = 38 B(9) = 49 ::::::::: and so on ... Is the number 123456789 a term in the given sequence? Work Done: I could solve the problem as shown below. But, then I have a different question at the end. Let B(n) be the n-th number in the given series and S(n) be the sum of its digits. For example: B(5) = 16 ==> S(5) = 1 + 6 = 7. B(n) = S(n) (mod 9) By definition, B(n+1) = B(n) + S(n) = {9*k + S(n)} + S(n) = 2*S(n) + 9*k ==> B(n+1) = {2*S(n)} (mod 9) ... (1) As B(n+1) = r (mod 9) AND S(n+1) = r (mod 9, we can say S(n+1) = {2*S(n)} (modulo 9) from (1). S(1) = B(1) = 1. S(1+1) = S(2) = 2*1 (mod 9) = 2 (mod 9) S(2+1) = S(3) = 2*2 (mod 9) = 4 (mod 9) S(3+1) = S(4) = 2*4 (mod 9) = 8 (mod 9) S(4+1) = S(5) = 2*8 (mod 9) = 16 (mod 9) = 7 (mod 9) S(5+1) = S(6) = 2*16 (mod 9) = 32 (mod 9) = 2*7 (mod 9) = 14 (mod 9) = 5 (mod 9) Similarly, S(7) = 1 (mod 9) and it continues in a similar fashion. B(1) = 1 modulo 9; B(2) = 2 modulo 9; B(3) = 4 modulo 9; B(4) = 8 modulo 9; B(5) = 7 modulo 9; B(6) = 5 modulo 9; B(7) = 1 modulo 9; and so on ... ==> B(n) = B(n - 6) modulo 9 for n > 6 In simple words ... S(1) = B(1) = 1 and S(n+1) = {2*S(n)} (modulo 9) implies S(n+1) = (2^n) (mod 9) = 1, 2, 4, 8, 7, 5 (mod 9) The number is 123456789. Sum of its digits = (1+2+3+4+5+6+7+8+9) = 45 = 9*5. 123456789 = 0 (mod 9) Sum of the digits of 1234565789 = 45 = 0 (mod 9) Therefore, 123456789 does not appear in the sequence. To even hold a chance its (modulo 9) should have been one of 1, 2, 4, 8, 7, or 5. This way I can be sure when a given number is not present in the sequence. But, is there any way by which we can be sure that a given number is present in the series when its 'modulo 9' is one of 1, 2, 4, 8, 7, or 5. For example: (a) 123456737 = 2 (mod 9) (b) 123456755 = 2 (mod 9) The above 2 numbers do not get disqualified in the first step. I used to computer program to find out B(3641312) = 123456755 where as 123456737 is not present in the series. I there any mathematical way to find this out. I am not able to proceed properly in the right direction. Please, help me. Thanks and regards, Shamik

Shamik,

Very nice question. The sequence is chaotic since it depends on the base 10, and the only way to settle the case of 123456737 may be to compute the whole sequence up to there.

I could not come with anything better than what you did. I asked myself whether 123456737 can even be written
as N + (sum of the digits of N), where N = 1 (mod 9). It is a necessary condition, though not sufficient. But I don't know if even this subquestion can be solved more efficiently than working out the whole sequence.

Claude

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.