Find the sum of digits of n+1,n+2.... when sum of digits of n is given

Question

We can easily compute the sum of digits of a given number but is there any mathematical formula or pattern we can use to determine the sum of next numbers without having to sum all the digits again and again?

For example

Sum of 1234 = 1+2+3+4 = 10
Sum of 1235 = 1+2+3+5 = 11
Sum of 1236 = 1+2+3+6 = 12

I can see some kind of pattern here but unable come up with any efficient math algorithm.

I use below method to calculate the sum of digits:

public int sum(long n) {  
    int sum = 0;   
    while (n != 0) {    
        sum += n % 10;
        n /= 10;  
    }  
    return sum;  
}

Which works fine but it is CPU intensive. I want to do this much faster. If I have a sequence of numbers, say 10->19 I should only have to count the digits for 10, then add one for each up to 19.

Is there any efficient way to calculate the sum of digits in numbers if I already have the sum of previous numbers?

Answer 1

DigitSum(n+1) = DigitSum(n) + 1 - (9 * NumberOfEndingZeros(n+1))

---

If you want to find not the digitsums of t consecutive numbers but the sum of the digitsums of t consecutive numbers (n+1, n+2, ..., n+t), it's simpler.

Sum(DigitSum(i)) for i = n+1 to n+t = a(n+t) - a(n)

where a(i) is the A037123 sequence from the Encyclopedia of Integer Sequences, which has several formulas. I think this will be quite fast:

a(n) = (1/2) * ( (n+1) * (n - 18 * sum{k>0, floor(n/10^k)} )
               + 9 * sum{k>0, (1+floor(n/10^k))*floor(n/10^k)*10^k}
               )