java查找n+1、n+2的数字之和。。。。当n的位数之和给定时

Question

我们可以很容易地计算一个给定数字的数字之和，但是有没有什么数学公式或模式可以用来确定下一个数字的和，而不必一次又一次地求所有数字的和

比如说

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

如果我已经有了以前数字的总和，有没有有效的方法来计算数字的总和

Answer 1

让我们来表示数字n的位数之和是s(n)

s(49) = 13

s(94) = 13

但是{}哪个{}，而{}哪个{}。因此，如果只给出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)

Answer 2

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}
               )

Answer 3

这是来自wikipedia的公式：

这是我的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;
}

Answer 4

最快的方法是提取每个数字，并在进行时添加

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纳秒。这会增加代码的复杂性。您必须使用第一个sumDigit来引导总和，因为您不能从1一直数到10^18