Number of digits of N factorial in base B

Question

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!.

A base-$b$ number of $d$ digits lies between $b^{d-1}$ and $b^d-1$. — , Apr 03 '17 at 07:09

score 1 · Accepted Answer · answered Apr 03 '17 at 08:10

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$.

Number of digits of N factorial in base B

1 Answers1