Башня степеней

[Sicker]

Пусть $a_0<<a_1<<a_2<<...<<a_n$, и пусть $(a_i_1,a_i_2,...a_i_n)$ обозначает $a_i_1^{a_i_2^{a_i_3^{...}}}$ где $(i_1,i_2,...i_n)$ - перестановка на множестве $(1,2,...n)$. Требуется указать алгоритм, который упорядочивает наборы $(a_i_1,a_i_2,...a_i_n)$ по возрастанию, а также в частности найти минимальный и максимальный элемент в нем.

[slavav]

Какие требования к алгоритму? Без них простое вычисление $n!$ пирамид и последующая сортировка тоже работают.

[Sicker]

slavav
А да, требований никаких нет, но вот числа $a_i$ очень большие, я забыл сказать. Например, $a_1=10^{10}$, $a_2=a_1^{a_1}$, $a_3=a_2^{a_2}$ и т.д. Либо что еще "покруче" возрастающее, как там например число грэмма, которое потом возводят в башню степеней самого себя числа грэмма раз, далее повторяется то же самое и т.д. Т.е. вычислить эту башню степеней невозможно

[wrest]

Sicker
То есть, по крайней мере, $e<a_0$, так?

[Sicker]

wrest
Да

[wrest]

Sicker

Sicker в сообщении #1378278 писал(а):

Т.е. вычислить эту башню степеней невозможно

А что возможно вычислить?

[slavav]

Тогда доказываем что $b < c \Leftrightarrow {a^b}^c > {a^c}^b$. И по индукции получаем максимум, если последовательность возрастает, и минимум если убывает.

[worm2]

Случай, когда все $a_i > e$, вроде бы, самый простой.
По крайней мере, минимальное число достигается при обратном упорядочении $(n, n-1, ..., 2, 1)$, а максимальное — при тождественной перестановке $(1, 2, ..., n)$.
Интереснее, когда есть числа меньше $e$, особенно — когда есть меньшие 1.
Когда все числа больше единицы, сравнительно легко установить отношение между результатами перестановок, отличающихся одной транспозицией соседних элементов. Пока что больше ничего не могу сказать.

[Sicker]

slavav в сообщении #1378285 писал(а):

Тогда доказываем что $b < c \Leftrightarrow {a^b}^c > {a^c}^b$.

У вас тут какая-то опечатка?

slavav в сообщении #1378285 писал(а):

И по индукции получаем максимум, если последовательность возрастает, и минимум если убывает.

А как именно по индукции?
А да, еще надо предъявить алгоритм упорядочивания

-- 25.02.2019, 12:25 --

worm2 в сообщении #1378286 писал(а):

По крайней мере, минимальное число достигается при обратном упорядочении $(n, n-1, ..., 2, 1)$, а максимальное — при тождественной перестановке $(1, 2, ..., n)$.

Верно, теперь предъявите общий алгоритм упорядочивания по возрастанию

[slavav]

Sicker в сообщении #1378297 писал(а):

slavav в сообщении #1378285 писал(а):

Тогда доказываем что $b < c \Leftrightarrow {a^b}^c > {a^c}^b$.

У вас тут какая-то опечатка?

Нет, это не опечатка. Это ошибка - неправильно расставил скобки в пирамиде.
Заметим, что $\frac{x}{\ln x}$ - монотонная функция для достаточно большого аргумента. Тогда
$b < c$

$\frac{b}{\ln b} < \frac{c}{\ln c}$

$b\ln c < c\ln b$

$c^b < b^c$

$a^{b^c} < a^{c^b}$.

[worm2]

Sicker в сообщении #1378297 писал(а):

предъявите общий алгоритм упорядочивания по возрастанию

Ну, я написал, что "самый лёгкий", но это самый лёгкий случай среди очень сложных Общего алгоритма у меня нет.
Есть только наблюдения, свидетельствующие о том, что он нетривиален.
Например, $3^{6^4}>4^{3^6}$, но $3^{7^4}<4^{3^7}$. Так что как-то надо считать.

[Sicker]

slavav в сообщении #1378303 писал(а):

Нет, это не опечатка. Это ошибка - неправильно расставил скобки в пирамиде.

Вот и славно
А распишите поподробнее индукцию

worm2 в сообщении #1378306 писал(а):

Есть только наблюдения, свидетельствующие о том, что он нетривиален.
Например, $3^{6^4}>4^{3^6}$, но $3^{7^4}<4^{3^7}$. Так что как-то надо считать.

Эти числа недостаточно удовлетворяют неравенству $>>$ для моей задачи.

[worm2]

Ну тогда опять всё просто
Нужно лексикографически упорядочить перевёрнутые последовательности $(i_n, i_{n-1}, ..., i_2, i_1)$ — это и будет порядком, в котором наши монстры возрастают.

[Sicker]

worm2
Что значит "лексиографически"?
Можно по-подробнее про способ упорядочивания?

[slavav]

Вот ещё цепочка:
$a << b$

$\ln a << \ln b$

$c\ln a << c\ln b$

$c\ln a + \ln\ln b << c\ln b + \ln\ln a$

$\ln(a^c\ln b) << \ln(b^c\ln a)$

$a^c\ln b << b^c\ln a$

$b^{a^c} << a^{b^c}$