找到你要的答案

Q:Sum of digits of a factorial

Q:阶乘的和的和

Link to the original problem

It's not a homework question. I just thought that someone might know a real solution to this problem.

I was on a programming contest back in 2004, and there was this problem:

Given n, find sum of digits of n!. n can be from 0 to 10000. Time limit: 1 second. I think there was up to 100 numbers for each test set.

My solution was pretty fast but not fast enough, so I just let it run for some time. It built an array of pre-calculated values which I could use in my code. It was a hack, but it worked.

But there was a guy, who solved this problem with about 10 lines of code and it would give an answer in no time. I believe it was some sort of dynamic programming, or something from number theory. We were 16 at that time so it should not be a "rocket science".

Does anyone know what kind of an algorithm he could use?

EDIT: I'm sorry if I didn't made the question clear. As mquander said, there should be a clever solution, without bugnum, with just plain Pascal code, couple of loops, O(n2) or something like that. 1 second is not a constraint anymore.

I found here that if n > 5, then 9 divides sum of digits of a factorial. We also can find how many zeros are there at the end of the number. Can we use that?

Ok, another problem from programming contest from Russia. Given 1 <= N <= 2 000 000 000, output N! mod (N+1). Is that somehow related?

链接到原来的问题

这不是作业问题。我只是认为有人可能知道这个问题的真正解决方法。

我是在一个编程大赛回到2004,有这个问题:

给定n,求n个数的和!n可以从0到10000。时限:1秒。我认为每个测试集最多有100个数字。

我的解决方案是相当快,但不够快,所以我只是让它运行一段时间。它建立了一系列预先计算的值,我可以用在我的代码。这是一个黑客,但它的工作。

但有一个家伙,谁解决了这个问题,约10行代码,它会给出一个答案,在任何时候。我相信这是某种动态规划,或者是数论。当时我们16岁,所以不应该是“火箭科学”。

有谁知道他可以使用哪种算法?

编辑:对不起,如果我没有明确的问题。正如mquander所说,应该有一个聪明的办法,没有bugnum,只是普通的Pascal代码,几圈,O(N2)或类似的东西。1秒不再是约束。

我发现在这里,如果n >;5,然后9分和一个阶乘的位数。我们还可以在数字的结尾找到多少个零。我们能用吗?

好,另一个来自俄罗斯编程竞赛的问题。给予1和LT;= N和LT;= 2,000,000,输出N!国防部(N + 1)。这是相关的吗?

answer1: 回答1:

I'm not sure who is still paying attention to this thread, but here goes anyway.

First, in the official-looking linked version, it only has to be 1000 factorial, not 10000 factorial. Also, when this problem was reused in another programming contest, the time limit was 3 seconds, not 1 second. This makes a huge difference in how hard you have to work to get a fast enough solution.

Second, for the actual parameters of the contest, Peter's solution is sound, but with one extra twist you can speed it up by a factor of 5 with 32-bit architecture. (Or even a factor of 6 if only 1000! is desired.) Namely, instead of working with individual digits, implement multiplication in base 100000. Then at the end, total the digits within each super-digit. I don't know how good a computer you were allowed in the contest, but I have a desktop at home that is roughly as old as the contest. The following sample code takes 16 milliseconds for 1000! and 2.15 seconds for 10000! The code also ignores trailing 0s as they show up, but that only saves about 7% of the work.

#include <stdio.h>
int main() {
    unsigned int dig[10000], first=0, last=0, carry, n, x, sum=0;
    dig[0] = 1;    
    for(n=2; n <= 9999; n++) {
        carry = 0;
        for(x=first; x <= last; x++) {
            carry = dig[x]*n + carry;
            dig[x] = carry%100000;
            if(x == first && !(carry%100000)) first++;
            carry /= 100000; }
        if(carry) dig[++last] = carry; }
    for(x=first; x <= last; x++)
        sum += dig[x]%10 + (dig[x]/10)%10 + (dig[x]/100)%10 + (dig[x]/1000)%10
            + (dig[x]/10000)%10;
    printf("Sum: %d\n",sum); }

Third, there is an amazing and fairly simple way to speed up the computation by another sizable factor. With modern methods for multiplying large numbers, it does not take quadratic time to compute n!. Instead, you can do it in O-tilde(n) time, where the tilde means that you can throw in logarithmic factors. There is a simple acceleration due to Karatsuba that does not bring the time complexity down to that, but still improves it and could save another factor of 4 or so. In order to use it, you also need to divide the factorial itself into equal sized ranges. You make a recursive algorithm prod(k,n) that multiplies the numbers from k to n by the pseudocode formula

prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)

Then you use Karatsuba to do the big multiplication that results.

Even better than Karatsuba is the Fourier-transform-based Schonhage-Strassen multiplication algorithm. As it happens, both algorithms are part of modern big number libraries. Computing huge factorials quickly could be important for certain pure mathematics applications. I think that Schonhage-Strassen is overkill for a programming contest. Karatsuba is really simple and you could imagine it in an A+ solution to the problem.


Part of the question posed is some speculation that there is a simple number theory trick that changes the contest problem entirely. For instance, if the question were to determine n! mod n+1, then Wilson's theorem says that the answer is -1 when n+1 is prime, and it's a really easy exercise to see that it's 2 when n=3 and otherwise 0 when n+1 is composite. There are variations of this too; for instance n! is also highly predictable mod 2n+1. There are also some connections between congruences and sums of digits. The sum of the digits of x mod 9 is also x mod 9, which is why the sum is 0 mod 9 when x = n! for n >= 6. The alternating sum of the digits of x mod 11 equals x mod 11.

The problem is that if you want the sum of the digits of a large number, not modulo anything, the tricks from number theory run out pretty quickly. Adding up the digits of a number doesn't mesh well with addition and multiplication with carries. It's often difficult to promise that the math does not exist for a fast algorithm, but in this case I don't think that there is any known formula. For instance, I bet that no one knows the sum of the digits of a googol factorial, even though it is just some number with roughly 100 digits.

我不知道是谁仍然关注这个线程,但无论如何。

首先,在官方看来链接的版本,它只能是1000阶乘,而不是10000阶乘。此外,当这个问题被重用在另一个编程竞赛,时间限制为3秒,而不是1秒。这使得你不得不努力获得一个足够快的解决方案的巨大差异。

其次,对于比赛的实际参数,彼得的解决方案是健全的,但一个额外的扭曲,你可以加快了5倍的32位架构。(即使是6的因素,如果只有1000!即,而不是与单个数字一起工作,在基100000中实现乘法运算。然后在最后,在每个超级数字的数字总数。我不知道你在比赛中有多好的电脑,但我在家里有一个桌面,几乎和比赛一样古老。下面的示例代码需要16毫秒为1000!2.15秒10000秒!代码也不为0尾随他们露面,但这不仅节省了约7%的工作。

#include <stdio.h>
int main() {
    unsigned int dig[10000], first=0, last=0, carry, n, x, sum=0;
    dig[0] = 1;    
    for(n=2; n <= 9999; n++) {
        carry = 0;
        for(x=first; x <= last; x++) {
            carry = dig[x]*n + carry;
            dig[x] = carry%100000;
            if(x == first && !(carry%100000)) first++;
            carry /= 100000; }
        if(carry) dig[++last] = carry; }
    for(x=first; x <= last; x++)
        sum += dig[x]%10 + (dig[x]/10)%10 + (dig[x]/100)%10 + (dig[x]/1000)%10
            + (dig[x]/10000)%10;
    printf("Sum: %d\n",sum); }

第三,有一个惊人的和相当简单的方法来加快计算的另一个相当大的因素。用现代方法进行大数相乘,不需要用二次时间计算n!相反,你可以在o-tilde做(n)的时间,其中的意味着你可以在对数因素。由于Karatsuba不把时间复杂度降到一个简单的加速度,但仍能改善它,可以节省4左右的另一个因素。为了使用它,你还需要将阶乘本身分解成相等大小的范围。你让一个递归算法(K,N)产品,将数字从K到N的伪代码公式

prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)

然后你用Karatsuba来做,结果大乘法。

比Karatsuba更好的傅里叶变换为基础的Schonhage Strassen乘法算法。碰巧,这两种算法都是现代大数库的一部分。计算阶乘的快速巨大可能对某些纯数学的应用是重要的。我认为Schonhage Strassen是一个编程大赛矫枉过正。Karatsuba是很简单的,你可以想象在一个+解决问题。


部分问题是一些猜测,有一个简单的数论伎俩,完全改变比赛的问题。例如,如果问题是确定n!国防部N + 1,然后Wilson定理说,答案是- 1时,N + 1是素数,这是一个很容易的演习,看到它的2时,N = 3,否则,当n + 1是复合。这也有变化,例如!同样是高度可预测的mod 2n + 1。也有同余和数字之间的一些关系。x国防部9的数字的总和也是X国防部9,这就是为什么总和是0国防部9时,x = N!n >;= 6。x国防部11的数字的交替和等于x国防部11。

问题是,如果你想要一个大的数字的总和,而不是模什么,从数论的招数用完了很快。加一个数字的数字与加法和乘法不相吻合。很难保证数学不存在一个快速算法,但在这种情况下,我不认为有任何已知的公式。例如,我敢打赌,没有人知道一个大数阶乘的位数之和,即使它只是大约100位数的数。

answer2: 回答2:

This is A004152 in the Online Encyclopedia of Integer Sequences. Unfortunately, it doesn't have any useful tips about how to calculate it efficiently - its maple and mathematica recipes take the naive approach.

这是在网上百科全书a004152整数序列。不幸的是,它没有任何有用的提示关于如何计算有效的Maple和Mathematica的食谱以幼稚的方法。

answer3: 回答3:

I'd attack the second problem, to compute N! mod (N+1), using Wilson's theorem. That reduces the problem to testing whether N is prime.

我会攻击第二个问题,计算n!国防部(N + 1),使用Wilson定理。这减少了问题,以测试是否N是素数。

answer4: 回答4:

Small, fast python script found at http://www.penjuinlabs.com/blog/?p=44. It's elegant but still brute force.

import sys
for arg in sys.argv[1:]:
    print reduce( lambda x,y: int(x)+int(y), 
          str( reduce( lambda x, y: x*y, range(1,int(arg)))))

 

$ time python sumoffactorialdigits.py 432 951 5436 606 14 9520
3798
9639
74484
5742
27
141651

real    0m1.252s
user    0m1.108s
sys     0m0.062s

小,在http://www.penjuinlabs.com/blog/快速找到Python脚本?P = 44。它的优雅,但仍然蛮力。

import sys
for arg in sys.argv[1:]:
    print reduce( lambda x,y: int(x)+int(y), 
          str( reduce( lambda x, y: x*y, range(1,int(arg)))))

 

$ time python sumoffactorialdigits.py 432 951 5436 606 14 9520
3798
9639
74484
5742
27
141651

real    0m1.252s
user    0m1.108s
sys     0m0.062s
algorithm  dynamic-programming  sum-of-digits