5
$\begingroup$

How do I estimate the number of digits of 333! in a rigorous way?

What I did so far is just counting in the following manner: 1 digit for the first 99 numbers and then 2 digits for the remaining 234 numbers of 333!. This sums up to approx. 567 digits. Which is very rough compared to 698 digits which is the real solution.

Any other suggestions?

$\endgroup$
5
  • $\begingroup$ What do you mean "mathematically"? Is there another, non-mathematical way to do it? Like "philosophically"? $\endgroup$
    – Klangen
    Commented Aug 26, 2019 at 11:06
  • 7
    $\begingroup$ Stirling's formula? $\endgroup$
    – lulu
    Commented Aug 26, 2019 at 11:06
  • $\begingroup$ $99$ is closer to adding two digits than it is to adding one digit when you multiply by it. $\endgroup$
    – Arthur
    Commented Aug 26, 2019 at 11:06
  • $\begingroup$ @Klangen, I am referring to a more rigorous and accurate way instead of a simple hand counting method. I edited the question. Thanks for the remark– $\endgroup$
    – Philipp
    Commented Aug 26, 2019 at 11:24
  • $\begingroup$ Throwing log(333!)/log(10) into WolframAlpha suggests the estimate of $698$ digits. Very rough upper and lower bounds suggests somewhere between $323$ and $1332$ digits; how precise would you like the estimate to be? $\endgroup$
    – Servaes
    Commented Aug 26, 2019 at 19:23

3 Answers 3

11
$\begingroup$

Stirling's approximation $$n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$ is spooky accurate. Take the (base-10) log of both sides, and you get $$\log n!\approx \frac{1}{2}(\log(2\pi)+\log n)+n(\log n-\log e)$$ $$= \frac{1}{2}\log(2\pi)-n\log e+\left(n+\frac{1}{2}\right)\log n$$ $$\approx 0.4-.43n+\left(n+\frac{1}{2}\right)\log n$$

Plugging $n=333$ into it, I get $698.45+$

$\endgroup$
5
  • $\begingroup$ Is the error may affect the result? $\endgroup$
    – MafPrivate
    Commented Aug 26, 2019 at 11:27
  • 1
    $\begingroup$ Once you take logarithms, the $\sim$ technically changes into something else. Not that $\sim$ is wrong, but it has a formal meaning in this case, and using it after taking logarithms undersells the accuracy of Stirling's approximation. $\endgroup$
    – Arthur
    Commented Aug 26, 2019 at 11:28
  • $\begingroup$ @Arthur thanks. I forget that $\sim$ has a technical definition. $\endgroup$
    – user694818
    Commented Aug 26, 2019 at 11:29
  • $\begingroup$ The approximation (and any errors I made along the way) affect the answer a little. According to W|A, $\log(333!)=697.014+$ $\endgroup$
    – user694818
    Commented Aug 26, 2019 at 11:39
  • $\begingroup$ Additionally, my problem was that I didn't remember how to calculate the digits of any number $n$ given an arbitrary base $b$: $1+\lfloor log_b (n) \rfloor$. In our case we have $1+\lfloor log_{10} (333!) \rfloor$. Applying Stirling's formula yields $1+\lfloor 697.0142 \rfloor = 698$. Is this reasoning correct? $\endgroup$
    – Philipp
    Commented Aug 26, 2019 at 12:31
3
$\begingroup$

For any (large) $N$ we have

$$\log(N!)=\sum_{k=1}^N\log k={1\over\ln10}\sum_{k=1}^N\ln k={1\over\ln10}\sum_{k=1}^N(\ln(k/N)+\ln N)={N\over\ln 10}\left(\ln N+{1\over N}\sum_{k=1}^N\ln(k/N)\right)\approx{N\over\ln10}\left(\ln N+\int_0^1\ln x\,dx\right)={N\over\ln10}(\ln N-1)$$

For $N=333$, this gives

$$\log(333!)\approx695.35$$

which suggests there are approximately $\lceil695.35\rceil=696$ digits in $333!$.

To be more rigorous about the integral approximation, we have

$$-1=\int_0^1\ln x\,dx\lt{1\over N}\sum_{k=1}^N\ln(k/N)\lt\int_{1/N}^1\ln x\,dx={\ln N+1\over N}-1$$

so

$${N\over\ln10}(\ln N-1)\lt\log(N!)\lt{N\over\ln10}(\ln N-1)+{\ln N+1\over\ln10}$$

which gives the following range for the number of digits:

$$696\le\lceil\log(333!)\rceil\le699$$

$\endgroup$
3
  • $\begingroup$ $\log N!=\log 2+\log 3+\sum_{k=4}^N\log k > \log 2+\log 3+\int_3^N\ln x\,\mathrm dx$ gives $\log(333!)>696.003$, so your $696$ can be improved to $697$. Unfortunately, $333!$ is just 3% above a power of $10$, hence to ultimately decide between the last two possibilities, we need quite some improvement on the lower estimate. $\endgroup$ Commented Aug 26, 2019 at 13:08
  • $\begingroup$ @BarryCipra, I think there should be a "$+$" instead a "$-$" in the numerator of the estimation of the upper bound: $$[...]\lt\int_{1/N}^1\ln x\,dx={\ln N +1\over N}-1$$, shouldn't it? $\endgroup$
    – Philipp
    Commented Aug 26, 2019 at 16:43
  • $\begingroup$ @Philipp, yes, thank you. It's fixed now. $\endgroup$ Commented Aug 26, 2019 at 18:28
1
$\begingroup$

What we want is the (integer part of) the value of $$ \log_{10}1 + \log_{10}2 + \cdots + \log_{10}333 + 1 $$ You found an approximation by assuming that every number in this sum below $\log_{10}100 = 2$ was equal to $1$, and every number $2$ or higher was equal to $2$. This will, as you have found, underestimate the true answer.

I think it would be one step better to round each of the numbers in the sum above to its closest integer instead, rather than rounding most of them down. Since $\sqrt{10} \approx 3.16$, that means that $\log_{10}3$ gets rounded down to $0$, everything from $\log_{10}4$ to $\log_{10}31$ gets rounded to $1$, everything from $\log_{10}32$ to $\log_{10}316$ gets rounded to $2$, and the remaining few get rounded to $3$. This gives a final answer of $$ 3\cdot 0 + 28\cdot 1 + 285\cdot 2 + 17\cdot 3 + 1= 650 $$ which is a lot closer to the true answer (48 away rather than 131 away).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .