The smallest number $m$, such that $m\uparrow \uparrow (n+1)>n\uparrow\uparrow n$

Question

A natural number $n\ge 3$ is given. Denote $a\uparrow\uparrow b$ to be a power tower of $b$ $a's$.

Let $m$ be the smallest natural number , such that $m\uparrow\uparrow(n+1) > n\uparrow\uparrow n$

How can I efficiently determine $m$, in particular if $n$ is very large.

Is there a formula $m(n)$ giving $m$ directly ?

Since $n\uparrow \uparrow (n+1)>n\uparrow\uparrow n$, we have $m\le n$.

It seems that $m\le n-1$ holds for $n\ge 4$.

Answer 1

Not a complete answer, but too cumbersome for a comment.

For nearly every value of $n$, the answer will be the largest value of $m$ such that $\frac{m^m}{m-1}$ is less than $n$. With a little work one can show that if $n \le m^{m-1}$ then $n\uparrow\uparrow n < m \uparrow\uparrow (n+1)$, whereas it is easy to see that if $n \ge \frac{m^m}{m-1}$ then $n\uparrow\uparrow n > m\uparrow\uparrow (n+1)$. Thus if $n$ is not between $m^{m-1}$ and $\frac{m^m}{m-1}$ for some value of $m$, then the above answer will be exact, whereas if $n$ lies between $x^{x-1}$ and $\frac{x^x}{x-1}$ then $m(n) = x$ for lower values and $m(n)=x+1$ for high values.

Determining the exact transition point seems tricky, and I think it is very likely there is no nice answer.

EDIT: Adding proofs.

If $n \le m^{m-1}$, then $n^n \le (m^{m-1})^{(m^{m-1})} = m^{m^{m} - m^{m-1}}$. Subsequent exponentiations are not enough to overcome the deficit; I will illustrate for $n\uparrow\uparrow 5$, and the pattern should be clear for all other power tower lengths.

$$n \uparrow\uparrow 5 = n^{n^{n^{n^n}}} < (m^m)^{(m^m)^{(m^m)^{m^{m^m - m^{m-1}}}}} = m^{m^{m^{m^{m^m - m^{m-1} + 1} + 1} + 1}} < m^{m^{m^{m^{m^m - m^{m-1} + 1} + 2}}} < m^{m^{m^{m^{m^m - m^{m-1} + 2}}}}< m^{m^{m^{m^{m^m}}}}.$$

If $n \ge \frac{m^m}{m-1}$, we have $n^n \ge (\frac{m^m}{m-1})^{\frac{m^m}{m-1}} > (m^{m-1})^{\frac{m^m}{m-1}} = m^{m^m}$. Subsequent exponentiations will only increase the advantage of the power tower of $n$'s, since it exponentiates to a higher base.

Answer 2

Since $\log(a↑↑b)=a↑↑(b-1)\cdot\log a$, we have \begin{align} m ↑↑ (n+1) &= n ↑↑ n \\ m ↑↑ n \cdot \log m &= n ↑↑ (n-1) \cdot \log n \\ m ↑↑ (n-1) \cdot \log m + \log \log m &= n ↑↑ (n-2) \cdot \log n + \log\log n \end{align} If we consider $m ↑↑ x \cdot \log m \gg \log\log m$, we could ignore double-log component and collapse the equation into $$ m^m \log m + \log\log m \approx n \log n+\log\log n$$

Comparing the solution of $m(4)$ from the exact equation and the one from the approximated equation, we see that the difference is within 1 per 50000: \begin{align} m_\text{exact}(4) &= \color{blue}{2.327}95742769995688307901467440\ldots \\ m_\text{approx}(4) &= \color{blue}{2.327}86275825488194671546517753\ldots \\ \end{align} (take the ceiling if you need a natural number.)

From the approximation we see that $m(n)$ is growing extremely slowly.

Answer 3

I think , I have proven that for natural $a,b\ge 2$, we have

$a^{a^a}>b^b\implies a\uparrow\uparrow(n+1)>b\uparrow\uparrow n$ for all $n\ge 2$

Could someone check the proof ?

It works as follows. The basic idea is that $S=kT$ implies $a^S=b^T\cdot (\frac{a^k}{b})^T$

If $(\frac{a^k}{b})^T\ge k$ holds for $S=a^a$ and $T=b$, then we can apply induction on $n$ because $T$ strictly increases in every step.

At the first step we have $k=\frac{a^a}{b}$. So, we have to prove the condition

$(\frac{a^\frac{a^a}{b}}{b})^b\ge \frac{a^a}{b}$. This is equivalent to $a^{(a^a-a)b}\ge b^b$. This is surely true, if $(a^a-a)b\ge a^a$ becuase then we have $a^{(a^a-a)b}\ge a^{a^a}>b^b$

But $(a^a-a)b\ge a^a$ is equivalent to $b\ge 1+\frac{1}{a^{a-1}-1}$

The right side of the last inequality is at most $2$ finishing the proof.

I think the proof (if actually correct) can be simplified.

I invite everyone not only to verify the proof, but also to find an easier proof.