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

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

• Could you give us "power tower" definition? – Tacet May 16 '16 at 21:32
• @Tacet $m \uparrow\uparrow 1 := m,~~ m \uparrow\uparrow (n+1) = m^{m \uparrow\uparrow n}$. – Anon May 16 '16 at 21:35
• @McFry Thank you. Problem looks interesting. Long time ago I spend some time on calculating "power tower" values modulo some numbers and this problem may be connected with solution to saving resources problem (which I didn't solve). +1 from me. – Tacet May 16 '16 at 21:43
• $m(3) = 2.11785593876346715155340948305\ldots$ by numerically solving $m^m \log m + \log\log m=3\log 3 +\log\log3$, it doesn't seem to have any nice representation though. Also it seems $m(4) = 2.32795742769995688307901467440\ldots$. – kennytm May 17 '16 at 9:26
• @kennytm I only search the smallest NATURAL number $m$ satisfying the inequality. – Peter May 17 '16 at 9:50

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.

• @Deedlit Is this approximation good enough to ensure that it gives the correct (natural) number for every $n$ ? – Peter May 17 '16 at 10:34
• Hmm, I'm not sure. The approximation is equivalent to finding m such that $m^{m^{m^m}}=n^{n^n}$. The question is whether we can have $m^{m^{m^m}}>n^{n^n}$ but $m^{m^{m^{m^m}}}<n^{n^{n^n}}$ for integers m,n. So we want to avoid $m^{m^m}\log m$ being between $n^n\log n$ and $n^n\log n + \log \log n$. Since $m^{m^m}$ increases quite rapidly compared to $\log \log n$, heuristically the probability of a counterexample should decrease quite rapidly, so if you check the small cases and find no counterexamples, you should have some confidence that there are none. Of course this is not a proof. – Deedlit May 17 '16 at 17:13
• For my puropses, it would be enough, especially because the method seems to be off by $1$ in the worst case. – Peter May 19 '16 at 10:50

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.

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.

• Please show a proof of the two implications. – Peter May 17 '16 at 9:48

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.

• @Deedlit Could you verify and/or simplify this proof ? This would be a very nice condition. And particular nice would be, if it could be extended to the condition $a\uparrow\uparrow(n+k)>b\uparrow\uparrow n$ – Peter Jun 12 '16 at 8:57