Оценка скорости возрастания последовательности

[Xenia1996]

Рассмотрим следующую бесконечную последовательность натуральных чисел:
$2, 72, 6810125783203125000000000000000=2^{15}*3^{20}*5^{24}, 2^{105}*3^{140}*5^{84}*7^{90}, ...$

Первый её член является наименьшим натуральным числом, которое при удвоении даёт квадрат натурального числа. Второй - при удвоении даёт квадрат, а при утроении -куб. Третий - ещё и пятую степень при упятерении, $n$-ый - наименьшее натуральное число, которое при умножении на каждое из первых $n$ простых чисел даёт степень натурального числа, показатель которой равен тому простому числу, на которое умножили это $n$-ый член.

Как оценить скорость возрастания этой последовательности? Возрастает ли она, скажем, быстрее, чем $2^{n!}$?

[ИСН]

Ох, страх какой.
Короче, на глаз получается (грубо) о-большое от exp(exp($n\ln n+n\ln\ln n$)). Где-то между $2^{n!}$ и $2^{(n!)^2}$.

[Xenia1996]

ИСН в сообщении #360334 писал(а):

Ох, страх какой.
Короче, на глаз получается (грубо) о-большое от exp(exp($n\ln n+n\ln\ln n$)). Где-то между $2^{n!}$ и $2^{(n!)^2}$.

Это на глаз. А на мозг?

[EtCetera]

Пусть $a_n$ - $n$-ый член данной последовательности. Тогда
$a_n=\prod\limits_{k=1}^{n}p_k^{\alpha_k^{(n)}}$, где $p_k$ - $k$-ое простое число, $\alpha_k^{(n)}$ - некоторый коэффициент, который должен удовлетворять следующим требованиям:
$\left\{\begin{array}{l}\alpha_k^{(n)}\equiv 0\mod p_m},\ m\ne k\ (1)\\ \alpha_k^{(n)}\equiv -1\mod p_k\ (2)\end{array}\right.$
Отсюда получаем, что
$\alpha_k^{(n)}=\dfrac{P_n}{p_k}\beta_k^{(n)}$, где $P_n=\prod\limits_{i=1}^n p_i$ ($P_0=1$), $\beta_k^{(n)}$ - некий натуральный коэффициент, учитывающий условие (2); в худшем случае он равен 1.
Тогда
$$a_n\ge \prod\limits_{k=1}^{n}p_k^{P_n/p_k}\ge\prod\limits_{k=1}^{n}p_k^{P_{n-1}}= P_n^{P_{n-1}}$
Но $P_{n-1}\ge n!$, поэтому $a_n\ge (n+1)!^{n!}$.
P.S. Забавно, но этой последовательности нет в OEIS.

[Xenia1996]

EtCetera в сообщении #360337 писал(а):

P.S. Забавно, но этой последовательности нет в OEIS.

Так добавьте её туда. Можете сослаться на меня. Сама я вряд ли на английский переведу ту *рень, что вперёд писала.

И, кстати, почему "забавно"? Всего имеется бесконечное множество целочисленных последовательностей. Ни один сервер (на сегодняшний день) не способен хранить бесконечное количество информации. В (далёком, или не очень (я, во всяком случае, доживу)) будущем появятся фрактальные компьютеры, принцип хранения информации в которых будет базироваться на том факте, что фрактал имеет бесконечную длину. Такие компьютеры смогут хранить бесконечное количество информации, а также обрабатывать её за нулевое время. И тогда, быть может, абсолютно все целочисленные последовательности смогут позволить себе храниться на сервере, размером с атом. А покамест хоть какой-то последовательности, да будет не доставать. А жаль.

[Joker_vD]

(Оффтоп)

Цитата:

Такие компьютеры смогут хранить бесконечное количество информации, а также обрабатывать её за нулевое время.

И теория сложности станет не нужна! Что-то не верится.

А где вообще такая последовательность возникла?

[EtCetera]

Кстати, для оценки сверху можно воспользоваться тем, что $\beta_k^{(n)}<p_k$. Тогда
$a_n\le\prod\limits_{k=1}^{n}p_k^{(P_n/p_k)\cdot(p_k-1)}\le\dfrac{\prod\limits_{k=1}^{n}p_k^{P_n}}{\prod\limits_{k=1}^{n}p_k^{P_n/p_k}}\le\dfrac{P_n^{P_n}}{P_n^{P_{n-1}}}=P_n^{P_n-P_{n-1}}$
Впрочем, без хорошей оценки сверху для $P_n$, ложно извлечь отсюда что-либо существенное.

[Xenia1996]

Joker_vD в сообщении #360458 писал(а):

(Оффтоп)

Цитата:

Такие компьютеры смогут хранить бесконечное количество информации, а также обрабатывать её за нулевое время.

И теория сложности станет не нужна! Что-то не верится.

А где вообще такая последовательность возникла?

Эту последовательность я придумала сама, решая следующую задачу:

Найти наименьшее целое положительное число, при удвоении которого получается квадрат, при утроении - куб, а при умножении на 5 - пятая степень целого числа.

Источник задачи: http://nsu.ru/phpBB/viewtopic.php?t=4205

(Оффтоп)

По поводу теории сложности: её можно обобщить на бесконечные множества, ведь бесконечное множество бесконечному множеству - тоже рознь (есть алеф-нуль, алеф-1, ...).

[arseniiv]

(Оффтоп)

О, я такую задачу как-то решал, только там было без тройки. До неё я думал, что совсем ничего не понимаю в теории чисел. Хотя сейчас я снова так думаю.

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

Xenia1996, Вам с Вашей тягой к большим числам срочно надо узнать про функцию Аккермана

[Xenia1996]

Профессор Снэйп в сообщении #360687 писал(а):

Xenia1996, Вам с Вашей тягой к большим числам срочно надо узнать про функцию Аккермана

Давно знаю. А Вы про нотацию Конвея знаете?
Вот ссылочка: http://en.wikipedia.org/wiki/Conway_cha ... w_notation

А вот симпатичный товарищ, который также не ровно дышит к большим числам: http://mrob.com/pub/index.html

Вот тут у него про числа: http://mrob.com/pub/math/numbers.html

А вот тут - про большие числа: http://mrob.com/pub/math/largenum.html

Там и про Аккермана, и про Конвея...