Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there any efficient algorithm for counting number of digits in n! without actually calculating n!?

[Addendum -- PLC]: I voted to close the question as "no longer relevant" because of Gerry's answer that one could just use Stirling's formula, as supplemented by a comment which referred to a formula of Kamenetsky given on the online journal of integer sequences. It seems now that it is an open question whether Kamenetsky's formula always (rather than just "most of the time") gives exactly the right answer, so there is more here than I had realized. A followup question which provides more context has been asked here:

How good is Kamenetsky's formula for the number of digits in n-factorial?

share|improve this question

closed as off topic by Steve Huntsman, Harald Hanche-Olsen, Pete L. Clark, François G. Dorais, Reid Barton Mar 24 '10 at 2:10

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

6  
This sounds like somebody's homework problem. –  Andrej Bauer Mar 23 '10 at 9:39
6  
I think marking this down is a bit harsh. It's not a poor, uninteresting or inappropriate question: experts in particular fields might have knowledge about this problem that is not widely documented or easily found. (+1 countermeasure) –  Rhubbarb Mar 23 '10 at 17:14
4  
I agree with rhubbarb that downvoting this and voting to close are a bit harsh. –  Kevin H. Lin Mar 23 '10 at 23:38
2  
In my opinion, reopening is not necessary, since a better phrased version of the question has already been asked: see the link in my addendum above. I agree that the downvoting now appears unjustified (I have just upvoted it, which more than compensates). –  Pete L. Clark Mar 24 '10 at 6:21

1 Answer 1

Counting the digits is the same problem as estimating the size (and then taking the logarithm to the base 10) so Stirling's formula (q.v.) and its refinements should do the trick.

share|improve this answer
8  
It means, "Google it." –  Jonas Meyer Mar 23 '10 at 5:54
15  
Good answer, Jonas. For the sake of completeness, q.v. abbreviates the Latin, "quod vide," which translates to "which see," which basically means, in the words of Casey Stengel (q.v.), "you could look it up." –  Gerry Myerson Mar 23 '10 at 6:03
3  
Sloane's research.att.com/~njas/sequences/A034886 gives the following note: Using Stirling's formula we can derive a formula, which is very fast to compute in practice: floor((log(2*pi*n)/2+n*(log(n)-log(e)))/log(10))+1. - Dmitry Kamenetsky (dkamen(AT)rsise.anu.edu.au), Jul 07 2008 –  Douglas S. Stones Mar 23 '10 at 9:44
1  
There was a discussion of the Kamenetsky formula in the Usenet newsgroup, sci.math, Subject: Number of digits in factorial, in January-February. The question was whether the formula was exact, or just an outstanding approximation. No proof of exactness was forthcoming, neither was any counterexample. –  Gerry Myerson Mar 23 '10 at 22:11
1  
See also an answer at Ask Dr. Math: mathforum.org/library/drmath/view/68245.html –  lhf Mar 24 '10 at 2:00

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