java - 开心数的最佳算法

给定的数字是n位数，找到2n位数
比如说
给定的数字是3，那么6n的数字是100000-999999
然后找出这些数字的计数，例如

       123213
1 + 2 + 3 = 2 + 1 + 3
        6 = 6

我找到并编写了一个计算小数字的程序，但我需要最快的算法来找到这些数字。思想？
我的程序：

Scanner scan = new Scanner(System.in);

System.out.println("enter  n ");

int say = scan.nextInt();

say *= 2;

int low = (int) Math.pow(10, say - 1);
int max = (int) Math.pow(10, say) - 1;

int counter = 0;

int first = 0;
int last = 0;

for (int i = low; i <= max; i++) {

    int number = i;
    first = 0;
    last = 0;

    for (int j = 0; j < say / 2; j++) {

        int k = number % 10;
        first += k;
        number /= 10;
    }

    for (int j = 0; j < say / 2; j++) {

        int k = number % 10;
        last += k;
        number /= 10;
    }

    if (first == last) {
        //  System.out.println(i);
        counter++;
    }
}
System.out.println(counter);

最佳答案

这些数字在俄语中被称为幸运券（ru.wikipedia.org）然而，除了a link，我似乎找不到一个好的英语解释。
基本上，假设我们有2n位数，我们希望第一个n的和等于最后一个n的和我们首先计算c(d,s)：具有sumd的s数字序列的数目在这里，0 <= d <= n和0 <= s <= 9n这可以通过动态编程来实现：c(0,0)=1，对于d > 0，c(d,s) = c(d-1,s-0) + c(d-1,s-1) + c(d-1,s-2) + ... + c(d-1,s-9)，因为我们可以获取任何d-1数字序列，并从0到9写入另一个数字。
现在，幸运券的总数是不同幸运券数的总和，其中第一个s数字的总和是n，最后一个s数字的总和是n。当s是固定的时，这个数字等于s：选择前半部分的方法有很多，选择第二部分的方法也有很多。
因此答案是c(n,s) * c(n,s)。
还有其他的解决方案也涉及到高等数学，但对于程序员的作业来说，这就足够了再一次，我找不到正确的英语来源-对不起！these slides是俄语中的一些流行文章，值得一提。
编辑：如果您实际上需要对数字100000到999999，而不是000000到999999进行解释，那么一个修补程序将计算c(n,s)，其中sum[s=0..9n] c(n,s)^2是同一个表，但在添加第一个数字时使用禁用的零位加法进行计算。