我们可以很容易地计算给定数字的数字总和，但是是否有任何数学公式或模式可以用来确定下一个数字的总和，而不必一次又一次地对所有数字求和？
例如
Sum of 1234 = 1+2+3+4 = 10
Sum of 1235 = 1+2+3+5 = 11
Sum of 1236 = 1+2+3+6 = 12
我可以在这里看到某种模式，但无法提出任何有效的数学算法。
我使用下面的方法来计算数字的总和：
public int sum(long n) {
int sum = 0;
while (n != 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
这工作正常，但它是 CPU 密集型的。我想更快地做到这一点。如果我有一个数字序列，假设10->19我只需要数 10 的数字，然后为每个数字加一个，直到 19。
如果我已经有了以前数字的总和，是否有任何有效的方法来计算数字的总和？
DigitSum(n+1) = DigitSum(n) + 1 - (9 * NumberOfEndingZeros(n+1))
如果你想找到的不是t连续数字的数字和，而是t连续数字的数字和（n + 1，n + 2，...，n + t），它更简单。
Sum(DigitSum(i)) for i = n+1 to n+t = a(n+t) - a(n)
其中a(i)是来自整数序列百科全书的A037123序列，它有几个公式。我认为这会很快：
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}
)
最快的方法是提取每个数字并随时添加。
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;
}
印刷
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
对于较大的值，它可以节省大约 70 ns。它给你的代码增加了一些复杂性。您必须使用第一个 sumDigit 来引导总和，因为您无法从 1 一直数到 10^18。
让我们表示一个数字的数字总和n是s(n)
s(49) = 13
s(94) = 13
但是49+1 = 50哪个s(50) = 5，94+1 = 95哪个s(95) = 14。因此，如果您只知道 的位数之和n是 13，那么对于 的位数之和，您至少有两个不同的可能答案n+1。 您需要一些有关 n 的附加信息。
我确实认为关键是知道如果 n 以 9 结尾，s(n+1)则最多为 s(n) - 9。（啊，这就是 ypercube 的答案所在。）所以如果你有 xxxx9（最后一个 x 不是9） s(xxxx9 + 1) = s(xxxx9) - 9 + 1，。如果您有 xxx99,s(xxx99 + 1) = s(xxx99) - 18 + 1等。
因此，如果您计算范围内的所有 10、100、数千等，可能会加快这一速度。
（再次，我看到 ypercube 击败了我）。看起来这正是 A037123 的公式所做的（但从 0 到 n）。（让我们称之为a(n)）
所以最后，既然你想要从 n 到 n+r 的数字总和，而不是从 1 到 n 的总和，我们需要看看我们是否可以推导出一个公式范围ss(n,n+r)
这似乎很简单
ss(n,n+r) = a(n+r) - a(n-1)
这是来自维基百科的公式：
这是我在 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;
}