3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ try $$n\approx 52$$ $\endgroup$
    – Dr. Sonnhard Graubner
    Sep 27, 2017 at 16:22
  • $\begingroup$ Well $\log (25!) = \sum \log k$ If we make it base three we log 3 to 8 about 1.5 on average. 9 to 25 about 2.5 on average so 50 is a really dirty first guess. $\endgroup$
    – fleablood
    Sep 27, 2017 at 16:24
  • 1
    $\begingroup$ D'oh $n \approx \log_3 25! = \sum \log_3 k \approx \int_{1}^{25} \log_3 x dx$. $\endgroup$
    – fleablood
    Sep 27, 2017 at 16:28
  • 2
    $\begingroup$ Stirling's formula $\log(n!)\approx n\log n-n+\frac{1}{2}\log(2\pi n)$ gives a very good approximation for $\log(25!)$. It is $58.00027...$ $\endgroup$
    – Eclipse Sun
    Sep 27, 2017 at 16:29

3 Answers 3

Reset to default
3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ it isn't true that $52.794 < 52 < 52.865$ $\endgroup$
    – user795305
    Sep 27, 2017 at 18:14
  • 1
    $\begingroup$ @Ben: No! The inequalities show that the integer number n in questions is $52,$ for $n\ge 53$ we have $25! < 3^n$ $\endgroup$
    – gammatester
    Sep 27, 2017 at 18:45
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ So, in general, we need a calculator to solve this kind of problem? @theophile $\endgroup$
    – akusaja
    Sep 27, 2017 at 16:31
  • 1
    $\begingroup$ @akusaja It doesn't hurt to have a calculator. There are faster ways than what I posted—I was just making a suggestion on how you could have continued—but in the end, you'll need to do a bit of number crunching. Stirling's approximation is very accurate and simplifies the work. $\endgroup$
    – Théophile
    Sep 27, 2017 at 16:44
  • $\begingroup$ But, if we use stirling's formula, it seems we must take our calculator too to count it? By the way, Thanks for your answer. For conclusion, if I want to use another solution, then stirling's formula is a better way? $\endgroup$
    – akusaja
    Sep 27, 2017 at 17:56
  • $\begingroup$ @akusaja Yes, you basically need a calculator at some point. In previous times, people would have looked up values on a chart of logarithms, but that's essentially the same thing. The other answer (with Stirling's formula) is a much better way than the one I gave because you need to calculate only the logarithm of $25$ (or $2\log5$), which is obviously more efficient than finding the logs of all primes up to $23$. $\endgroup$
    – Théophile
    Sep 27, 2017 at 19:22
3
$\begingroup$

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.

Newton Raphson for different X0

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

$\endgroup$
3
  • 1
    $\begingroup$ Very nice idea! $\endgroup$
    – Théophile
    Sep 27, 2017 at 19:40
  • $\begingroup$ @Théophile Thanks :) $\endgroup$
    – Jam
    Sep 27, 2017 at 19:42
  • $\begingroup$ @Jam +1) good answer :) $\endgroup$
    – Zaharyas
    Sep 27, 2017 at 22:05

You must log in to answer this question.

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