Number Theory – Accuracy of Stirling’s Formula for $n!$ Digits

number theory

It is known that the number of digits of a natural number $n > 0$, which represent by $d(n)$ is given by:

$d(n)= 1 + \lfloor\log n\rfloor\qquad (\text{I})$

($\log$ indicates $\log$ base $10$)

Well .. the classical approach to the Stirling factorial natural number $n > 1$ is given by:

$$n! \approx f(n) = [(2n\pi) ^{1/2}] [(n / e) ^ n]$$

The number of digits $n!$, according to equality (I), is:

$d(n!) = 1 + \lfloor\log n!\rfloor$

It seems to me that for all natural $n> 1$, $\log n!$ and $\log [f (n)]$ have the same floor:

$$\lfloor\log(n!)\rfloor = \lfloor\log(f(n))\rfloor$$

Here's my big question!

Therefore, we could write:

$$d (n!) = 1 + \lfloor\log(f(n))\rfloor$$

Hope someone has some little time for the theme.

Best Answer

6561101970383 is a counterexample, and the first such if I computed correctly. See my answer in https://mathoverflow.net/questions/19170 for more information.

Related Solutions

Number Theory – Using Floor, Ceiling, Square Root, and Factorial Functions to Get Integers

I've numerically verified that this is possible for all numbers up to 208. Here's a heuristic argument why we can expect it to be possible for all numbers:

After the last factorial, the remaining operations are floors, ceilings and square roots. The natural number $n$ is reachable from a number $m$ using these operations iff $(n-1)^{2^k}<m<(n+1)^{2^k}$ for some $k\in\mathbb N_0$: If this condition is fulfilled, we can draw $k$ square roots and then take either the floor or the ceiling to reach $n$; if it isn't fulfilled, then taking the floor or ceiling in between drawing square roots won't help, since it will never cause the value to cross the boundaries $(n\pm1)^{2^k}$. (Note that the expressions for $n$ up to $11$ reflect this; the floor or ceiling operations are never directly followed by a square root.)

Taking logarithms, we have that $n$ is reachable from $m$ iff $2^k\ln(n-1)<\ln m<2^k\ln(n+1)$. If we consider the logarithm of $m$ to be "randomly" distributed, we can ask for the "probability" of a factorial fulfilling this condition. The length of the admissible interval is $2^k(\ln(n+1)-\ln(n-1))$, and this has to be put in relation to the distance between successive intervals, which is $2^{k+1}\ln n-2^k\ln n=2^k\ln n$. (This is the distance to the next higher interval; the distance to the next lower interval is $2^{k-1}\ln n$, but the difference isn't relevant in what follows.)

Thus, the proportion of values fulfilling the condition is $2^k(\ln(n+1)-\ln(n-1))/(2^k\ln n)=(\ln(n+1)-\ln(n-1))/\ln n$. The exact value isn't important; the key point is that this is independent of $k$ and thus doesn't decrease as $m$ increases. Thus, for each $m$, the "probability" of $m$ fulfilling the condition is roughly the same, as long as it makes sense to regard the logarithm of $m$ as uniformly distributed. But we know that infinitely many values of $m$ are reachable, namely at the very least the ones we get by repeatedly taking factorials, starting with $4$, and it's plausible that there is no systematic relationship between these values and the above intervals, so that the logarithms of these values of $m$ can be regarded as uniformly distributed. Since for any given $n$ each of these values of $m$ has the same finite probability of $n$ being reachable from it, we can expect to eventually find some $m$ from which $n$ is reachable.

Summing discrete 3d coordinate lengths

OPs approach is fine and in fact the examples already present all possible different variants of the number of digits $k_1,k_2,k_3$ of the three dimensions with $k_1+k_2+k_3=n$ digits.

All three dimensions are equal: $\qquad\qquad\ k_1=k_2=k_3$
Two are equal, the third is different: $\qquad\ k_1=k_2, k_1\ne k_3$
All three are pairwise different: $\qquad\qquad\; k_1\ne k_2, k_1\ne k_3, k_2\ne k_3$

As there are some different cases to distinguish we conveniently use Iverson brackets.

Let $n\ge 3$. We start with \begin{align*} \sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} &\left\{\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^3[[k_1=k_2=k_3]]\right.\tag{1}\\ &\qquad+3\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)\\ &\qquad\qquad\cdot[[k_1=k_2,k_1\ne k_3]]\\ &\qquad+3\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)^2\tag{2}\\ &\qquad\qquad\cdot[[k_1\ne k_2,k_2= k_3]]\\ &\qquad\left.+6\prod_{j=1}^3\left(10^{k_j}-10^{k_j-1}[[k_j>1]]\right)[[k_1\ne k_2,k_1\ne k_3,k_2\ne k_3]]\right\}\tag{3} \end{align*}

We can simplify the three summands (1), (2) and (3) somewhat.

Case 1: All three dimensions are equal

We obtain \begin{align*} \sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}}&\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^3[[k_1=k_2=k_3]]\\ &=\sum_{{1\leq k_1= k_2= k_3\leq n}\atop{k_1+k_2+k_3=n}}\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^3\\ &\,\,\color{blue}{=\left(10^{\frac{n}{3}}-10^{\frac{n}{3}-1}[[n>3]]\right)^3[[3|n]]}\tag{4} \end{align*}

Since $k_1=k_2=k_3$ we have only one case to consider, namely $3k_1=n$ resp. $k_1=\left\lfloor\frac{n}{3}\right\rfloor$. This implies that $n$ has to be a multiple of $3$ which is asserted by $[[3|n]]$, otherwise the sum is zero.

Case 2: Two are equal, the third is different

We obtain \begin{align*} &3\sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)\\ &\qquad\qquad\cdot[[k_1=k_2,k_1\ne k_3]]\\ &\qquad+3\sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)^2\\ &\qquad\qquad\qquad\cdot[[k_1\ne k_2,k_2= k_3]]\\ &\quad=3\sum_{{1\leq k_1= k_2< k_3\leq n}\atop{2k_1+k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)\\ &\qquad+3\sum_{{1\leq k_1< k_2= k_3\leq n}\atop{k_1+2k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)^2\\ &\quad\,\,\color{blue}{=3\sum_{k_1=1}^{\left\lfloor\frac{n-1}{3}\right\rfloor} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{n-2k_1}-10^{n-2k_1-1}\right)}\\ &\qquad\,\,\color{blue}{+3\sum_{k_3=\left\lceil\frac{n+1}{3}\right\rceil}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \left(10^{n-2k_3}-10^{n-2k_3-1}[[n-2k_3>1]]\right)\left(10^{k_3}-10^{k_3-1}\right)^2}\tag{5} \end{align*}

The upper limit $\left\lfloor\frac{n-1}{3}\right\rfloor$ of the left-hand sum in (5) follows from the index region \begin{align*} &1\leq k_1=k_2<k_3\leq n\\ &2k_1+k_3=n\qquad\qquad\qquad\to\qquad k_3=n-2k_1>k_1\qquad\to\qquad k_1<\frac{n}{3}\\ \end{align*}

The lower limit $\left\lceil\frac{n+1}{3}\right\rceil$ of the right-hand sum in (5) follows from the index region \begin{align*} &1\leq k_1<k_2=k_3\leq n\\ &k_1+2k_3=n\qquad\qquad\qquad\to\qquad k_1=n-2k_3<k_3\qquad\to\qquad k_3>\frac{n}{3}\\ \end{align*}

The upper limit $\left\lfloor\frac{n-1}{2}\right\rfloor$ of the right-hand sum in (5) follows from the index region \begin{align*} &1\leq k_1<k_2=k_3\leq n\\ &k_1+2k_3=n\qquad\qquad\qquad\to\qquad n-2k_3\geq 1\qquad\to\qquad k_3\leq \frac{n-1}{2}\\ \end{align*}

Case 3: All three are pairwise different

We obtain \begin{align*} &6\sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} \prod_{j=1}^3\left(10^{k_j}-10^{k_j-1}[[k_j>1]]\right)[[k_1\ne k_2,k_1\ne k_3,k_2\ne k_3]]\\ &\qquad=6\sum_{{1\leq k_1< k_2< k_3\leq n}\atop{k_1+k_2+k_3=n}} \prod_{j=1}^3\left(10^{k_j}-10^{k_j-1}[[k_j>1]]\right)\\ &\qquad\,\,\color{blue}{=6\sum_{k_1=1}^{n-2}\sum_{k_2=k_1+1}^{\left\lfloor\frac{n-k_1-1}{2}\right\rfloor}\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_2}-10^{k_2-1}\right)}\\ &\qquad\qquad\qquad\qquad\qquad\color{blue}{\cdot\left(10^{n-k_1-k_2}-10^{n-k_1-k_2-1}\right)}\tag{6} \end{align*}

Putting (4) - (6) together gives a simplified formula of (1) - (3).

The upper limit $\left\lfloor\frac{n-k_1-1}{2}\right\rfloor$ of the sum in (6) follows from the index region \begin{align*} &1\leq k_1< k_2< k_3\leq n\\ &k_1+k_2+k_3=n\qquad\qquad\to\qquad k_3=n-k_1-k_2>k_2\qquad\to\qquad k_2<\frac{n-k_1}{2}\\ \end{align*}

Best Answer

Related Solutions

Number Theory – Using Floor, Ceiling, Square Root, and Factorial Functions to Get Integers

Summing discrete 3d coordinate lengths

Related Question