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

  • $\begingroup$ Could you give us "power tower" definition? $\endgroup$ – Tacet May 16 '16 at 21:32
  • 2
    $\begingroup$ @Tacet $m \uparrow\uparrow 1 := m,~~ m \uparrow\uparrow (n+1) = m^{m \uparrow\uparrow n}$. $\endgroup$ – Anon May 16 '16 at 21:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Tacet May 16 '16 at 21:43
  • $\begingroup$ $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$. $\endgroup$ – kennytm May 17 '16 at 9:26
  • $\begingroup$ @kennytm I only search the smallest NATURAL number $m$ satisfying the inequality. $\endgroup$ – 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.

enter image description here

  • $\begingroup$ @Deedlit Is this approximation good enough to ensure that it gives the correct (natural) number for every $n$ ? $\endgroup$ – Peter May 17 '16 at 10:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Deedlit May 17 '16 at 17:13
  • $\begingroup$ For my puropses, it would be enough, especially because the method seems to be off by $1$ in the worst case. $\endgroup$ – 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.

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.

  • $\begingroup$ Please show a proof of the two implications. $\endgroup$ – 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.

  • $\begingroup$ @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$ $\endgroup$ – Peter Jun 12 '16 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.