Рекурсивная последовательность

[nikov]

$$f(1, x) = x + 1$$

$f(n + 1, x) = f(n,f(n,\dots f(n, x) \dots ))$ - в правой части $f$ повторяется $x$ раз

$$a(n) = f(n, 2)$$

Последовательность $a(n)$ начинается $3,4,8,2048.$ Надо вычислить $a(5)$ или хотя бы указать для него верхнюю границу.

[maxal]

Удобнее писать $f_n(x)$ вместо $f(n,x)$.
Как нетрудно видеть,
$f_1(x) = x+1$
$f_2(x) = 2x$
$f_3(x) = 2^x x$
$f_4(x) = f_3^{(x)}(x)$
$f_5(x) = f_4^{(x)}(x) = f_4^{(x-1)}(f_4(x))$
...
Поэтому, в частности,

$$a(5) = f_5(2) = f_4(f_4(2)) = f_4(2048)=f_3^{(2048)}(2048)$$

Воспользовавшись оценкой $f_3(x) \geq 2^x$ получаем, что $a(5)$ больше башенки $2^{2^{2^\dots}}}$ в которой 2048 этажей и на последнем стоит число 2048. Это огромнейшее число, которое не то, что вычислить, а даже оценить более-менее точно не получится.

[ИСН]

Смахивает на функцию Аккермана, но эта ещё хуже.

[Профессор Снэйп]

ИСН писал(а):

Смахивает на функцию Аккермана, но эта ещё хуже.

Да, действительно смахивает. Очередная разновидность функции Аккермана.

[Хорхе]

Свеженькая
http://www.research.att.com/~njas/sequences/A154714

Цитата:

Vladimir Reshetnikov (v.reshetnikov(AT)gmail.com), Jan 14 2009