3
$\begingroup$

Let $f_2(n)=2^n n$ and let $f_3$ be defined recursively as $$ f_3(n)=\underbrace{f_2\cdots f_2}_{n\text{ times}}(n)=f_2^n(n). $$ This will lead to tetration, but is it possible to write $f_3$ in a closed formula, using the notation ${^{n}a}$ for tetration (or even Knuth's up-arrow notation)?

I tried to write a simple code to see an emerging pattern, but simplifications seem somehow tricky. Also, ${^{n}2}$ seems to be relatively simple to recognise in the expansion of $f_3$, but the remaining terms are somewhat complicated and it almost feels like the expression behaves like a fractal. Any ideas?

Here are the first four iterations, might help to picture the pattern. \begin{align*} f_2(n)&=2^n n\\ f_2^2(n)&=2^{(2^n+1)n}n=2^{2^nn}2^nn\\ f_2^3(n)&=2^{(2^{(2^{n}+1)n}+2^n+1)n}n=2^{2^{2^nn}2^nn}2^{2^nn}2^nn\\ f_2^4(n)&=2^{(2^{(2^{(2^n+1)n}+2^n+1)n}+2^{(2^n+1)n}+2^n+1)n}n \end{align*} Just to give some context, these functions were defined and discussed in a recent Numberphile video about $\text{TREE}(n)$ and Graham's number (see around minute $10$).

$\endgroup$
  • $\begingroup$ Look at this page : sites.google.com/site/largenumbers which is a superb survey over the world of large numbers. $\endgroup$ – Peter Nov 3 '19 at 12:15
  • 1
    $\begingroup$ @Peter Looks very interesting, I'll take a look! $\endgroup$ – sam wolfe Nov 3 '19 at 12:33
  • $\begingroup$ @Peter I noticed you've already seen my other question on nested tetration. The original motivation comes from this question (see draft answer below). I'm thankful for your help. $\endgroup$ – sam wolfe Nov 3 '19 at 12:44
  • $\begingroup$ TREE(3) is already a completely other league compared to the much,much,much,much smaller Graham-number. $\endgroup$ – Peter Nov 3 '19 at 12:47
1
$\begingroup$

The simple answer is no, because there's a mix of operations being iterated: either multiplication and exponentiation, or if you bring the multiplication up a level, addition and exponentiation.

As far as approximations go though, you can see here for some tight bounds:

$$n\operatorname{Tet}(2^n,1,n)\le f_3(n)\le\operatorname{Tet}(2\sqrt[n]n,n,n)$$

where $\operatorname{Tet}(a,b,c)=\underbrace{a~\widehat~~a~\widehat~~\dots~\widehat~~a~\widehat~~}_cb$ is $c$ powers of $a$ with $b$ on top.

$\endgroup$
  • $\begingroup$ For some reason the LaTeX isn't compiling on the link you gave. $\endgroup$ – sam wolfe Nov 20 '19 at 12:00
  • 1
    $\begingroup$ The site no longer supports MathJax as it used to. You can copy the text over there onto here and it will render if you wish to see the proof of the above inequalities. $\endgroup$ – Simply Beautiful Art Nov 20 '19 at 14:43
  • $\begingroup$ Thank you! Could you please expand a bit more on why the mix of operations makes it impossible to simplify (check my answer below)? I understand the difficulty, but not the impossibility of it. $\endgroup$ – sam wolfe Nov 20 '19 at 15:07
  • $\begingroup$ @samwolfe Tetration and the like simply do not involve iterating mixed combinations of operations, and one can clearly see this grows about as fast as tetration, and nothing other than tetration unless you clarify grows that fast. $\endgroup$ – Simply Beautiful Art Nov 20 '19 at 22:23
  • $\begingroup$ The fact that I'm trying to use tetration to express an iterative expression in closed form does not justify that I can't do it. All I need to simplify are nested tetrations, and that is potentially impossible (why?). I'm afraid, however, that your answer does not answer my question, but I appreciate your effort. $\endgroup$ – sam wolfe Nov 20 '19 at 23:12
0
$\begingroup$

I believe I've found a potential solution. $f_3$ may be expressed as $$ f_3(n)=\log_2\left(g^{n}\left(2^n \right) \right), $$ where $g(n)={}^2n$. Indeed, iterating over $g$, which corresponds to the iterations of $f_2$, we have \begin{align} f_2(n)&=\log_2\left(g\left(2^n \right) \right)=\log_2\left(2^{2^nn} \right)=2^nn\\ f_2^2(n)&=\log_2\left(g^2\left(2^n \right)\right)=\log_2\left({}^2(2^{2^nn} )\right)=\log_2\left(2^{2^{2^nn}2^nn} \right)=2^{2^nn}2^nn\\ f_2^3(n)&=\log_2\left(g^3\left(2^n \right)\right)=\log_2\left({}^2({}^2(2^{2^nn} ))\right)=\log_2\left(2^{2^{2^{2^nn}2^nn}2^{2^nn}2^nn} \right)=2^{2^{2^nn}2^nn}2^{2^nn}2^nn\\ &\vdots \end{align} It is then clear that the only simplification remaining is of the following $$ g^n(a)={}^{\overbrace{2\,\cdots\, 2}^{n\text{ times}}}a. $$ While in general it is not true that ${}^a({}^bn)={}^{ab}n$, a closed formula for $g^n(a)$ might be possible. Any comments are appreciated. A follow-up question can be found here.

Note: Even though this is not a full solution, I decided to post it as an answer in order to present my ideas more clearly.

Edit note: Based on a comment by @r.e.s., I simplified a bit my original expression for $f_3$ by noticing that $g(2^n)=2^{2^nn}$.

$\endgroup$
  • 1
    $\begingroup$ Note that $g(2^n)=2^{2^nn},$ so we can also write $f_3(n)=\log_2\left(g^n\left(2^n \right) \right).$ $\endgroup$ – r.e.s. Nov 3 '19 at 5:08
  • $\begingroup$ @r.e.s. Good point, thank you. I will edit my answer based on your comment. $\endgroup$ – sam wolfe Nov 3 '19 at 12:34

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.