How to find the maximum integer value of n such that 25! > $3^n$

Question

I have a question about permutation and inequality.

In this question, I've meet with the permutation of big number.

The question is How to find the maximum integer value of n such that 25! > $3^n$ ?

At my first thought, I think I must use logarithm to the both sides such that:

$log(25!) > nlog(3)$

Then, I can easily got:

$n<$ $\frac{log(25!)}{log(3)}$

But, I've found the problem because the number(25!) is too big to count by hand, and also the log value of permutation isn't easy to calculate by hand.

Can anybody provide the easier way to find the maximum integer value of n for this case? I think we need a formula to tackle a problem, but I didn't find the easy way to solve this problem.

For the answer, I used my calculator and find out the maximum integer value of n is 52.

Answer 1

'I think I must use logarithm to the both sides' is a good start. To get valid bounds, use the last formula in the introduction to Stirling's approximation (with $k$ instead of $n$) $$\sqrt{2\pi}\ k^{k+\frac{1}{2}}e^{-k} \le k! \le e\ k^{k+\frac{1}{2}} e^{-k}$$ which is valid for all positive integers $k.$ Substituting $k=25$ and taking logarithms gives $$\ln(25!) \ge \ln\sqrt{2\pi}+25.5\ln( 25) - 25 \approx 58.000$$ $$\ln(25!) \le 1 + 25.5\ln (25) -25 \approx 58.082$$ Dividing by $\ln 3$ you get for the real solution $x$ of $25!=3^x$ the bounds

$$\frac{58.000}{\ln 3}\approx 52.794 < x < 52.865 \approx \frac{58.082}{\ln 3}$$

and therefore your value is $\boxed{n=52},$ because we are searching an integer $n.$

Answer 2

If you want to continue with logarithms, use the following two properties: $$\begin{align} \log(ab) &= \log a + \log b,\\ \log(a^k) &= k\log a \end{align} $$

Thus, $$\begin{align} \log(25!) &= \log(25\cdot24\cdot23\cdots1)\\ &=\log(25) + \log(24) + \log(23) + \cdots + \log(1)\\ &=\log(5^2) + \log(2^33) + \log(23) + \cdots + \log(1)\\ &=2\log(5) + 3\log2+\log3 + \log(23) + \cdots + 0\\ &=\ldots \end{align} $$

After collecting all like terms, you will have to calculate only the logarithms of each prime from $2$ to $23$.

Answer 3

Method

This method gives a sequence that should converge to $n$ and could feasibly be done by hand, if given sufficient time. Define $f(x)=\frac{25!}{3^x}-1$.* We will aim to find $x$, such that $f(x)=0.$ The Newton-Raphson method for finding the roots of $f$ is $x_{k+1}=x_k-\frac{3^{x_k}}{25!\ln3}+\frac1{\ln3}$. We can use the approximations $\ln(3)\approx0.910$ and $3^x=e^{x\ln3}\approx e^{1.10x}$ and $\frac{1}{25!\ln3}\approx e^{-58.1}$,** to arrive at the following sequence:

$$x_{k+1}=x_k-e^{1.10x_k-58.1}+0.910$$

The figure below shows $y=x_k$ for $k$ up to $20$, for different starting values: $x_0=10,20,30,40$. The limit of the sequence should be $y\approx 52$, which is the $n$ we were looking for.

Analysis

The sequence, seems to approach $y\approx52.732$ when $x_0<52$. However, when $x_0>52$, it seems to diverge.

Whether it's easier to compute $25!$ or $e^{1.10x_k-58.1}$ by hand is hard to say, since you'd have to do long computations either way. However, for large $k$, $x_{k+1}=x_k$. This means that $e^{1.10x_k-58.1}=0.910\approx e^0$ so we can use the Maclaurin series of $e^x$ to quickly compute $e^{1.10x_k-58.1}$. Another advantage the Newton-Raphson method has is that calculation errors can be mitigated by continuing in the sequence; as long as your $x_k$ is near $n$, you should, in theory, approach $n$ by finding $x_{k+1}$. This isn't the case for computing $25!=25\times24\times\ldots$, where an error could be disastrous.

But you should note that we have used approximations in generating our sequence. And, if we didn't have a calculator, we may not know if we're approaching $n$ or $n+1$ or something else; were our approximations accurate enough? We may also need the values of constants like $\ln5$ and $\ln\pi$ but, even in a world without calculators these could be in lookup tables.

---

* We may be tempted to define $f(x)=25!-3^x$ but the sequence this generates converges extremely slowly to $n$. This is probably due to its very steep slope near $n$ so I used a function with a shallower slope.

** This can be calculated with Stirling's Approximation as $\begin{aligned}\ln\left(\frac{1}{25!\ln3}\right)&\approx-\ln\left(\sqrt{25\cdot2\pi}\cdot\left(\frac{25}{e}\right)^{25}\right)-\ln\ln3\\&\approx25-51\ln5-\frac12\ln{2\pi}-\ln\ln3\\&\approx-58.1\end{aligned}$