2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Рекурсивная последовательность
Сообщение15.01.2009, 11:32 
$$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)$ или хотя бы указать для него верхнюю границу.

 
 
 
 
Сообщение15.01.2009, 12:18 
Аватара пользователя
Удобнее писать $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. Это огромнейшее число, которое не то, что вычислить, а даже оценить более-менее точно не получится.

 
 
 
 
Сообщение15.01.2009, 12:28 
Аватара пользователя
Смахивает на функцию Аккермана, но эта ещё хуже.

 
 
 
 
Сообщение15.01.2009, 13:21 
Аватара пользователя
ИСН писал(а):
Смахивает на функцию Аккермана, но эта ещё хуже.


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

 
 
 
 
Сообщение15.01.2009, 23:47 
Аватара пользователя
Свеженькая :)
http://www.research.att.com/~njas/sequences/A154714
Цитата:
Vladimir Reshetnikov (v.reshetnikov(AT)gmail.com), Jan 14 2009

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group