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

Question

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

for instance

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 see some kind of pattern here, but I can not find an effective mathematical algorithm.

I use the method below 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's the processor intensity. I want to do it a lot faster. If I have a sequence of numbers, say 10->19 , I will only need to count the numbers for 10, and then add one for each to 19.

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

Answer 1

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

---

If you want to find not the digits t consecutive numbers, but the sum of the digits t consecutive numbers (n + 1, n + 2, ..., n + t), this is 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 whole sequences, which has several formulas. I think it will be pretty 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} ) 

Answer 2

The fastest way is to extract each digit and add it along the way.

 public static void main(String... args) { // check values int runs = 1000000; for (int i = 100; i < runs; i++) { int sum = sumDigits(i - 1); int sum1 = sumDigits(i); int sum2 = sumDigits(sum, i); if (sum1 != sum2) throw new AssertionError(i + ": " + sum1 + " != " + sum2); } long start = System.nanoTime(); for (int i = 0; i < runs; i++) { int sum = sumDigits(i); // prevent optimising away. if (sum < 0) throw new AssertionError(); } long time = System.nanoTime() - start; System.out.printf("sumDigits took an average of %,d ns%n", time / runs); long start2 = System.nanoTime(); int lastSum = 0; for (int i = 0; i < runs; i++) { int sum = sumDigits(lastSum, i); lastSum = sum; // prevent optimising away. if (sum < 0) throw new AssertionError(); } long time2 = System.nanoTime() - start2; System.out.printf("sumDigits using previous value took an average of %,d ns%n", time2 / runs); long large = Long.MAX_VALUE - runs - 1; long start3 = System.nanoTime(); for (int i = 0; i < runs; i++) { int sum = sumDigits(large + i); // prevent optimising away. if (sum < 0) throw new AssertionError(); } long time3 = System.nanoTime() - start3; System.out.printf("sumDigits took an average of %,d ns%n", time3 / runs); long start4 = System.nanoTime(); int lastSum2 = sumDigits(large); for (int i = 0; i < runs; i++) { int sum = sumDigits(lastSum2, large + i); lastSum2 = sum; // prevent optimising away. if (sum < 0) throw new AssertionError(); } long time4 = System.nanoTime() - start4; System.out.printf("sumDigits using previous value took an average of %,d ns%n", time4 / runs); } public static int sumDigits(long n) { int sum = 0; do { sum += n % 10; n /= 10; } while (n > 0); return sum; } public static int sumDigits(int prevSum, long n) { while (n > 0 && n % 10 == 0) { prevSum -= 9; n /= 10; } return prevSum + 1; } 

prints

 sumDigits took an average of 32 ns sumDigits using previous value took an average of 10 ns sumDigits took an average of 79 ns sumDigits using previous value took an average of 7 ns 

At high values, it can save about 70 ns. This adds some complexity to your code. You must use the first sumDigit to bootstrap the amount, because you cannot read the entire path from 1 to 10 ^ 18.

Answer 3

Denote the sum of the digits of n is s(n)

s(49) = 13

s(94) = 13

but 49+1 = 50 , which s(50) = 5 , and 94+1 = 95 , which s(95) = 14 . Therefore, if you were only given that the sum of the digits n is 13, you have at least two different possible answers for the sum of the digits n+1 . Need more information about n.

I really think the key knows that if n ends with 9, s(n+1) will be at most s (n) - 9. (Ah, where the ypercube answer is.) So, if you have xxxx9 (where the last x is nothing but 9), s(xxxx9 + 1) = s(xxxx9) - 9 + 1 . If you have xxx99, s(xxx99 + 1) = s(xxx99) - 18 + 1 , etc.

So, what can speed it up if you count all 10, 100, thousands, etc. in its range.

(Again, I see that ypercube beat me before the hit). It seems that the formula for A037123 does just that (but from 0 to n). (Lets call it a(n) )

So, finally, since you want to get the sum of the sum of the digits from n to n + r, and not the sum from 1 to n, we need to see if we can get the formula for the sum of the sum of the digits for the range ss(n,n+r)

It will be easy

ss(n,n+r) = a(n+r) - a(n-1)

Answer 4

This is the formula from wikipedia :

This is my implementation in Java:

 public static int digitSum(int x) { return IntStream.rangeClosed(0, (int) Math.log10(x)) // From zero to the number of digits of x in base 10... .map(n -> (x % (int) Math.pow(10, n + 1) - x % (int) Math.pow(10, n)) / (int) Math.pow(10, n)) // ...yield each digit... .sum() // and sum; }