Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to find the digit sum of $n!$ ($n \in \mathbb{N} \text{ and } n \le100$) without actually computing the factorial?

I faced this problem in quantitative aptitude test which asks to find the sum of the digits of $25!$, I was wondering if there is any paper pencil approach to deduce the sum from counting the number of each digits in the factorial without actually computing the whole thing.

share|improve this question
2  
Related: stackoverflow.com/questions/1469529/… –  Matt N. Nov 7 '11 at 8:34
1  
In the present form of the question, the answer is "yes, obviously"; there are lots of ways of doing that -- for instance you can take out all factors of $2$ and $5$ and use only the excess of one of them over the other; then you've chopped off the terminal $0$s and never compute $n!$. So to make this an interesting question you'll have to make some quantitative specification how much easier the method should be than actually computing the factorial. –  joriki Nov 7 '11 at 8:56
2  
You can find the digit sum mod nine very easily: any natural number $m$ is congruent to its digit sum mod 9. If $n\geq 6$ then $9 | n!$ so the digit sum has to be zero mod 9... –  mt_ Nov 7 '11 at 9:12
    
@ mt_:I think it's called digital root, but I don't want that here. –  Quixotic Nov 7 '11 at 10:09
add comment

1 Answer

By "without actually computing the whole thing", I'm going to assume you mean "without actually computing factorial in the traditional, brute force, way", i.e. "show any possible shortcut".... let's take a look at 25! because some of the paper-and-pencil approaches will apply to higher numbers as well...

First let's write out the factors of the numbers from 2 to 25: 2,3,2*2,5,2*3,7,2*2*2,3*3,2*5,11,2*2*3,13,2*7,3*5,2*2*2*2,17,2*3*3,19,2*2*5,3*7,2*11,23,2*2*2*3,5*5

Counting up the factors, we have 22 2s, ten 3s, etc, that is, 25! can be written as: 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23

As joriki says, we can toss tens, so let's toss out 6 5s and 6 2s:

2^16 * 3^10 * 7^3 * 11^2 * 13 * 17 * 19 * 23

We can make it still easier on ourselves by factoring out some numbers that are easier for us to work with on paper. For example, it's easy to multiply by 1001, and 1001 is 7*11*13, so let's separate those 3 factors out:

2^16 * 3^10 * 7^2 * 11 * 17 * 19 * 23 * 1001

Likewise 99 is easy to work with, so let's get that out:

2^16 * 3^8 * 7^2 * 17 * 19 * 23 * 1001 * 99

And 98 is only a little harder than 99 is:

2^15 * 3^8 * 17 * 19 * 23 * 1001 * 99 * 98

And finally, 102 is also just two away from 100:

2^14 * 3^7 * 19 * 23 * 1001 * 99 * 98 * 102

Come to think of it, 98 * 102 is 9,996, just four away from 10,000:

2^14 * 3^7 * 19 * 23 * 1001 * 99 * 9,996

And multiplying by 9 is easier than 3 so:

2^14 * 3 * 9^3 * 19 * 23 * 1001 * 99 * 9,996

We're out of tricks at this point, so let's go for it. Let's do the big primes now: 19 * 23 = 437.

Then multiply by 9 3 times: 4370 - 437 = 3933 39330 - 3933 = 35397 353970 - 35397 = 318573

And multiply by 3 once:

318573 * 3 = 955719

Then double this 14 times. (Hope I'm not the only one who finds it easy to double numbers?)

1911438 3822876 7645752 15291504 30583008 61166016 122332032 244664064 489328128 978656256 1957312512 3914625024 7829250048 15658500096

The only factors we have left are 1001, 99, and 9,996. Let's do that last one first... it's 10,000-4, so we'll double two more times:

31317000192 62634000384

And then subtract:

156585000960000 - 62634000384 =156522366959616

Multiply by 99:

15652236695961600 - 156522366959616 =15495714329001984

And finally multiply by 1001:

15495714329001984000 + 15495714329001984 =15511210043330985984

Finally, you can add up those digits.

1+5+5+1+1+2+1+0+0+4+3+3+3+0+9+8+5+9+8+4=72

as mt_ mentions, we expect the result to be evenly divisible by 9, so 72 sounds quite plausible.

p.s. Note to the stackexchange sysops: the trend on this question seems to be to post comments (not answers) to the original question. I would gladly do that, but since I still have a low rep, I am barred from posting comments.

share|improve this answer
    
Good, but you can use LaTeX here (a substantial subset thereof). Encase with dollars or double dollars. use \cdot for star (times). Not too hard, looks great too. :) –  J. W. Perry Jan 16 at 8:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.