Пусть ^ означает право-ассоциативный оператор возведения в степень, т.е. a^b^c = a^(b^c). Например, 2^3^2 = 2^(3^2) = 512. Во избежание недоразумений заметим, что в общем случае a^b^c ≠ a^(b*c).

Рассмотрим выражения вида a₁^a₂^...^aₙ, где каждый из операндов aₖ равен 2 или 3.

Требуется написать программу, которая будет печатать эти выражения, упорядоченные по их численным значениям. Программа должна быть способна распечатать сотни тысяч выражений за приемлемое время. Ошибки в распечатке из-за ошибок округления (равно как и по другим причинам) не допускаются. Для ясности, вот ожидаемое начало распечатки:

2
3
2^2
2^3
3^2
2^2^2
3^3
3^2^2
2^2^3
2^3^2
3^2^3
3^3^2
2^2^2^2
3^2^2^2
2^3^3
3^3^3
2^3^2^2
3^3^2^2
2^2^2^3
3^2^2^3
2^2^3^2
3^2^3^2
2^3^2^3
3^3^2^3
3^3^3^2
2^2^2^2^2
3^2^2^2^2
2^3^2^2^2
3^3^2^2^2
2^2^3^3
3^2^3^3
2^3^3^3
3^3^3^3
2^2^3^2^2
...

Соответствующие численные значения (вычислять или печатать их не требуется):

2
3
4
8
9
16
27
81
256
512
6561
19683
65536
43046721
134217728
7625597484987
2417851639229258349412352
443426488243037769948249630619149892803
115792089237316195423570985008687907853269984665640564039457584007913129639936
...

N>Требуется написать программу, которая будет печатать эти выражения, упорядоченные по их численным значениям. Программа должна быть способна распечатать сотни тысяч выражений за приемлемое время.

Альтернативно, написать программу, которая принимает порядковый номер N (начиная с 1) выражения в этой распечатке, и печатает соответствующее выражение. Для N < 10^6 время выполнения задачи должно быть порядка нескольких секунд или меньше.

N>Для ясности, вот ожидаемое начало распечатки:
среди первых членов ряда присутствует 2^3^3^3 (=2^7625597484987), но отсутствует 2^3^3^2 (=2^19683), которое очевидно меньше.
либо у меня проблемы с арифметикой, либо одно из двух.

need moar numberz

Здравствуйте, nikov, Вы писали:

N>Требуется написать программу, которая будет печатать эти выражения, упорядоченные по их численным значениям. Программа должна быть способна распечатать сотни тысяч выражений за приемлемое время. Ошибки в распечатке из-за ошибок округления (равно как и по другим причинам) не допускаются. Для ясности, вот ожидаемое начало распечатки:

Предлагаю такой подход.
Написать генератор программы, который находит первый миллион выражений за произвольное время, оформляет их в массив строковых литералов, а дальше всё просто

Здравствуйте, Muxa, Вы писали:

N>>Для ясности, вот ожидаемое начало распечатки:
M>среди первых членов ряда присутствует 2^3^3^3 (=2^7625597484987), но отсутствует 2^3^3^2 (=2^19683), которое очевидно меньше.
M>либо у меня проблемы с арифметикой, либо одно из двух.

Значит, вкралась ошибка

N>Значит, вкралась ошибка
Так а можно больше чисел (штук 100) и без ошибок? А то закончил на самом интересном.
Или это проблема?

Здравствуйте, Muxa, Вы писали:

N>>Значит, вкралась ошибка
M>Так а можно больше чисел (штук 100) и без ошибок? А то закончил на самом интересном.

Правильное начало здесь (операторы ^ для простоты опущены).

Здравствуйте, nikov, Вы писали:

M>>Так а можно больше чисел (штук 100) и без ошибок? А то закончил на самом интересном.

N>Правильное начало здесь (операторы ^ для простоты опущены).

Триллионный (10^12-й) член равен 3222222222223222323223232232323322232222.
Член с номером 10^100 равен

3222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222
3222333322232333232222232323222322223322223223223323232323232233333223233222322223222333222322222232
2333223323232223332233333323222223332233223222332232222333322322332322223323233322333332332222332232
32233232232232332323322322322322

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

Здравствуйте, Muxa, Вы писали:

M>Алгоритм построение этого ряда чисел я понял, но чтобы его закодировать без багов у меня уйдёт пара дней, не меньше.
M>Боюсь этот твой этюд не для меня

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

Здравствуйте, Кодт, Вы писали:

К>Предлагаю такой подход.
К>Написать генератор программы, который находит первый миллион выражений за произвольное время, оформляет их в массив строковых литералов, а дальше всё просто

Поймал

Ну ладно, вычисление a_n должно занимать сублинейное время от n.
По поводу константы — моя реализация находит одно значение a_n для n<10^5000 за время меньше секунды.
Список a_n для n=1..10^5 строится тоже меньше секунды. Хотя это наверняка можно ускорить, если переписать на C.

N>На самом деле он кодируется в несколько строчек, если уловить идею.
N>Написание строгого доказательства корректности может занять некоторое время (оно несколько рутинное), хотя понять его интуитивно и набросать основные моменты можно тоже в несколько строчек.

Видимо у нас с тобой разные алгоритмы.
Мой строит двоичное дерево "двоечки налево, троечки направо", в котором путь от корня до каждого узла соответствует числу из ряда.
Также все узлы пронумерованы хитрым способом согласно позиции числа в результируещем ряду.

В твоем алгоритме присутствует дерево в каком либо виде?