Алгоритм сравнения степенных башень

[nikov]

Даны две степенные башни, построенные из двоек и троек (наподобие $2^{3^{3^{2^2}}}$). Нужно определить, значение какой из них больше. Высота башень может быть большой, так что непосредственное вычисление может быть неподъёмным. Известен ли какой-то эффективный алгоритм для сравнения?

Мне пока приходят в голову приемы, работающие в некоторых частных случаях, например: поиск одной последовательности в качестве подпоследовательности в другой (с возможной заменой двоек на тройки), двукратное логарифмирование.

-- Вт фев 08, 2011 05:27:23 --

Ещё такой вопрос возник: Существует ли предел $\lim \limits_{n \to \infty}\underbrace{\log_2 \log_2 \dots \log_2}_n \underbrace{3^{3^{\cdot^{\cdot^{3}}}}}_n$?
Если да, то выражается ли он через известные математические константы?

[Sonic86]

Про предел. Последовательность обозначим $a_n$, $a_1 = \log _2 3$, $a_n = \log _2 (3 \cdot \log _2 (3 \cdot ...)) = \log _2 (3 \cdot a_{n-1}) = \log _2 3 + \log _2 a_{n-1}$. Предел скорее всего существует и является решением уравнения $a = \log _2 3 + \log _2 a$ (хе! решений уравнения 2!). Можно попробовать доказать, что $a_n$ ограничена сверху и снизу... А вообще это метод простых итераций для функции $\varphi (x) = \log _2 3 + \log _2 x$, его сходимость проверяется стандартно.

-- Вт фев 08, 2011 12:08:29 --

nikov писал(а):

двукратное логарифмирование.

$n$-кратное при необходимости

-- Вт фев 08, 2011 12:13:08 --

Высота башень обязательно одинакова или нет?

[venco]

Sonic86 в сообщении #410412 писал(а):

Про предел. Последовательность обозначим $a_n$, $a_1 = \log _2 3$, $a_n = \log _2 (3 \cdot \log _2 (3 \cdot ...)) = \log _2 (3 \cdot a_{n-1}) = \log _2 3 + \log _2 a_{n-1}$. Предел скорее всего существует и является решением уравнения $a = \log _2 3 + \log _2 a$

Что-то численно у меня другое значение получилось.
5-ое значение отличается от 4-ого в 16-ом знаке после запятой.
И значение это 2.444021461489203821...
А 6-е значение, по моим оценкам, отличается где-то в 60-ти миллионном знаке.

[nikov]

Sonic86 в сообщении #410412 писал(а):

Про предел. Последовательность обозначим $a_n$, $a_1 = \log _2 3$, $a_n = \log _2 (3 \cdot \log _2 (3 \cdot ...)) = \log _2 (3 \cdot a_{n-1}) = \log _2 3 + \log _2 a_{n-1}$.

Похоже, что это не совсем та последовательность, предел которой я искал. Различия начинаются с третьего члена.

Цитата:

nikov писал(а):

двукратное логарифмирование.

$n$-кратное при необходимости

Если у башень одинаковые основания - то да (но этот случай покрывается поиском подпоследовательности). Иначе я не вижу, как более чем двукратное логарифмирование поможет в сравнении.

Цитата:

Высота башень обязательно одинакова или нет?

Высота может быть разной.

-- Вт фев 08, 2011 23:06:27 --

venco в сообщении #410586 писал(а):

Что-то численно у меня другое значение получилось.
И значение это 2.444021461489203821...

У меня такой же численный результат получается.

[nikov]

Интересно, а как выглядит график функции $f(x)=\lim \limits_{n \to \infty}\underbrace{\ln \ln \dots \ln}_n \underbrace{x^{x^{\cdot^{\cdot^{x}}}}}_n$?

[nikov]

Мне подсказали дискуссию в sci.math на очень похожую тему: http://groups.google.com/group/sci.math/browse_thread/thread/93d87112f9118389/d83915421ad217d5

[worm2]

nikov в сообщении #410816 писал(а):

Интересно, а как выглядит график функции $f(x)=\lim \limits_{n \to \infty}\underbrace{\ln \ln \dots \ln}_n \underbrace{x^{x^{\cdot^{\cdot^{x}}}}}_n$?

Выскажу предположение, что он (на бесконечности) сильно похож на график функции $\ln\ln x^x=\ln x+\ln\ln x$.