0
$\begingroup$

This question already has an answer here:

Given the decimal integers N and B. How can the number of digits in N! in base B be calculated without calculating the value of N!?

Example: If N = 5 and B = 2, then N! = 5! = 120. Representing the value in base B, we get 1111000 which has 7 digits.

But I'm trying to get the result without calculating the value of N!.

$\endgroup$

marked as duplicate by Chris Culter, Community Apr 3 '17 at 8:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Hint: $\lceil\log_bN!\rceil$. $\endgroup$ – Yves Daoust Apr 3 '17 at 6:50
  • $\begingroup$ Would you please explain? $\endgroup$ – Shajid Apr 3 '17 at 7:01
  • $\begingroup$ A base-$b$ number of $d$ digits lies between $b^{d-1}$ and $b^d-1$. $\endgroup$ – Yves Daoust Apr 3 '17 at 7:09
1
$\begingroup$

The number of digits is $\lfloor\log_b N!\rfloor+1$. This can be rewritten as $$\Big\lfloor\sum_{r=1}^N\log_br\Big\rfloor+1.$$ That sum should be possible to calculate on computer even for relatively large $N$. However, you can also approximate it using Stirling's formula:$$\ln N!\approx(N+1/2)\ln N-N+\ln\sqrt{2\pi}.$$ To convert this to what you want, use the fact that $\log_bx=\frac{\ln x}{\ln b}$.

This approximation is pretty good. For $\log_25!$ it gives $6.883$, whereas the actual value is $6.907$.

$\endgroup$

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