2
$\begingroup$

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?

$\endgroup$
4
  • 6
    $\begingroup$ This sounds like somebody's homework problem. $\endgroup$ Mar 23, 2010 at 9:39
  • 8
    $\begingroup$ 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) $\endgroup$
    – Rhubbarb
    Mar 23, 2010 at 17:14
  • 6
    $\begingroup$ I agree with rhubbarb that downvoting this and voting to close are a bit harsh. $\endgroup$ Mar 23, 2010 at 23:38
  • 2
    $\begingroup$ 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). $\endgroup$ Mar 24, 2010 at 6:21

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
6
  • 9
    $\begingroup$ It means, "Google it." $\endgroup$ Mar 23, 2010 at 5:54
  • 15
    $\begingroup$ 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." $\endgroup$ Mar 23, 2010 at 6:03
  • 4
    $\begingroup$ 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 $\endgroup$ Mar 23, 2010 at 9:44
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 23, 2010 at 22:11
  • 1
    $\begingroup$ See also an answer at Ask Dr. Math: mathforum.org/library/drmath/view/68245.html $\endgroup$
    – lhf
    Mar 24, 2010 at 2:00

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