Sum of factorial digits

Question

Link to the original problem

This is not a homework question. I just thought that someone might know the real solution to this problem.

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

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

My solution was pretty quick, but not fast enough, so I just let it work for a while. He built an array of pre-calculated values ​​that 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 he would give an answer as soon as possible. I think it was some kind of dynamic programming or something like number theory. We were 16 at the time, so this should not be "rocket science."

Does anyone know which algorithm he could use?

EDIT : Sorry if I did not raise the question clearly. As mquander said, there must be a smart solution, without bugnum, with a simple Pascal code, a couple of loops, O (n ² ) or something like that. 1 second is no longer a limitation.

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

Well, another problem from the programming contest from Russia. Given 1 <= N <2,000,000,000, the output is N! mod (N + 1). Is this somehow connected?

Answer 1

I'm not sure who is still paying attention to this topic, but here it is all the same.

Firstly, in the official linked version, it should be only 1000 factorials, not 10,000 factorials. In addition, when this problem was reused in another programming contest, the time limit was 3 seconds, not 1 second. This greatly affects how difficult it is to work in order to get a fast enough solution.

Secondly, for the real parameters of the competition, Peter’s solution sounds, but with one additional twist you can speed it up 5 times with 32-bit architecture. (Or even a factor of 6, if only 1000 is required!) Namely, instead of working with individual numbers, implement multiplication in the base of 100000. Then sum the numbers in each super-sign at the end. I don’t know how good the computer that you allowed in the competition, but I have a desktop computer at home that is about as old as the competition. The following code example is 16 milliseconds per 1000! and 2.15 seconds for 10,000! The code also ignores trailing 0s as they appear, but this 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); } 

Thirdly, there is an amazing and fairly simple way to speed up the calculation using another significant factor. Using modern methods of multiplying large numbers to calculate n! No quadratic time required. Instead, you can do this in the O-tilde (n), where the tilde means you can throw logarithmic factors. There is a simple acceleration due to Karatsuba , which does not bring time complexity before, but still improves it and can save another factor 4 or so. To use it, you also need to divide factorial into equal ranges. You create a recursive prod (k, n) algorithm that multiplies numbers from k by n using the pseudo-code 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.

Even better than Karatsuba - this is the Schonhage-Strassen multiplication algorithm based on the Fourier transform. As it happens, both algorithms are part of modern libraries of a large number. Computing huge factorials quickly can be important for some pure math applications. I think that Schonhage-Strassen is too much for a programming contest. Karatsuba is really simple, and you can imagine it in solving the A + problem.

---

Part of the question posed is some speculation that there is a simple trick in number theory that completely changes the problem of competition. For example, if the question was to determine n! mod n + 1, then Wilson’s theorem states that the answer is -1 when n + 1 is simple, and it’s really a simple exercise to see that it is 2 for n = 3 and otherwise 0 when n + 1 is composite . There are variations of this; for example n! mod 2n + 1 is also very predictable. There are also some links between congruences and sums of numbers. The sum of the digits x mod 9 is also equal to x mod 9, so the sum is 0 mod 9 for x = n! for n> = 6. The variable sum of digits x mod 11 is x mod 11.

The problem is that if you want to get the sum of the digits of a large number, and not modulo anything, tricks from number theory end pretty quickly. Adding digits to numbers is not well related to adding and multiplying by hyphens. It is often difficult to promise that mathematics does not exist for a fast algorithm, but in this case I do not think that there is any known formula. For example, I'm sure no one knows the sum of the digits of the googol factorial, although these are just a few digits with about 100 digits.

Answer 2

This is A004152 's Online Integer Sequence Encyclopedia . Unfortunately, he does not have useful tips on how to calculate it correctly - his maple and mathematics recipes take a naive approach.

Answer 3

I would attack the second problem to calculate N! mod (N + 1) using Wilson's theorem . This reduces the problem to checking if N is prime.

Answer 4

A small quick python script is found at http://www.penjuinlabs.com/blog/?p=44 . It is an elegant yet 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 

Answer 5

Suppose you have large numbers (this is the least of your problems, assuming N is really big, not 10000) and continue from there.

The trick below is the N factor! factoring all n <= N, and then calculate the degrees of factors.

There is a vector of counters; one counter for each prime number up to N; set them to 0. For each n <= N, the coefficient n and, accordingly, increase the counters of prime coefficients (multiply the coefficient: start with small primes, construct primes in factorization and remember that dividing by 2 is a shift). Subtract counter 5 from counter 2 and make the counter equal to 5 zero (nobody cares about factors 10 here).

Edit

calculate all primes to N, run the next loop

 for (j = 0; j< last_prime; ++j) { count[j] = 0; for (i = N/ primes[j]; i; i /= primes[j]) count[j] += i; } 

end of editing

Note that in the previous block we used (very) small numbers.

For each simple factor P, you need to calculate P for the power of the corresponding counter, which takes the registration time (counter) using iterative squaring; now you need to multiply all these powers of primes.

In general, you have about N log (N) operations with small numbers (log N simple factors) and Log N Log (Log N) operations with large numbers.

Edit

and after improving editing, only N operations on small numbers.

end of editing

NTN

Answer 6

1 second? Why can't you just calculate n! and add numbers? These are 10,000 multiplications and no more than several tens of thousands of additions, which should take about one millionth of a second.

Answer 7

We'll see. We know that computing n! for any sufficiently large number it will ultimately lead to a number with a large number of trailing zeros that do not contribute to the sum. How about dropping zeros along the way? This will allow to slightly reduce the size of the item?

Hm. Nope. I just checked, and integer overflow is still a big problem even then ...

Answer 8

You must calculate the fat.

1 * 2 * 3 * 4 * 5 = 120.

If you only want to calculate the sum of digits, you can ignore trailing zeros.

For 6! you can do 12 x 6 = 72 instead of 120 * 6

For 7! you can use (72 * 7) MOD 10

EDIT.

I wrote the answer too fast ...

10 is the result of two primes 2 and 5.

Every time you have these 2 factors, you can ignore them.

 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15... 1 2 3 2 5 2 7 2 3 2 11 2 13 2 3 2 3 2 3 5 2 7 5 2 3 

Factor 5 appears in 5, 10, 15 ...
Then, after multiplying by a finite zero, 5, 10, 15 ...

We have many two and three ... We will soon overflow: - (

Then you still need the library for large numbers.

I deserve to be leveled!

Answer 9

Even without integers of arbitrary precision, this should be rude. In the statement of the problem you are contacting, the biggest factor to be calculated will be 1000 !. This is a number with approximately 2500 digits. So just do it:

• Allocate an array of 3000 bytes, with each byte representing one digit in the factorial. Start with a value of 1.
• Re-multiply the school class by an array to calculate the factorial.
• Make up the numbers.

Performing repeated multiplications is the only potentially slow step, but I am sure that 1000 multiplications can be performed per second, which is the worst case. If not, you can pre-compute a few milestone values ​​and simply paste them into your program.

One potential optimization: Exclude trailing zeros from the array when they appear. They will not affect the answer.

NORMAL NOTE: I take an approach to programming and competition. You will probably never do this in a professional job.

Answer 10

another solution using BigInteger

  static long q20(){ long sum = 0; String factorial = factorial(new BigInteger("100")).toString(); for(int i=0;i<factorial.length();i++){ sum += Long.parseLong(factorial.charAt(i)+""); } return sum; } static BigInteger factorial(BigInteger n){ BigInteger one = new BigInteger("1"); if(n.equals(one)) return one; return n.multiply(factorial(n.subtract(one))); }