OEIS A002845: количество различных значений, принимаемых 2 ^ 2 ^... ^ 2 (с n 2 и круглыми скобками, вставленными всеми возможными способами)

Я ищу достаточно быстрый алгоритм для вычисления терминов последовательности OEIS A002845. Позвольте мне повторить здесь свое определение.

Обозначим через ^ оператор экспоненциальности. Рассмотрим выражения вида 2 ^ 2 ^... ^ 2, имеющие n 2 с круглыми скобками, вставленными всеми возможными способами (число возможных скобок дается выражением Каталонские числа). Некоторые из этих выражений будут иметь такое же значение, например (2 ^ 2) ^ 2 = 2 ^ (2 ^ 2). Нас интересует число различных значений для данного n.

Существует явное решение грубой силы путем прямого вычисления этих выражений, но ясно, что требуемое время и пространство быстро превышают все разумные пределы даже при относительно малых n. Меня интересует многочленное решение этой проблемы.

Ответ 1

Просто укажите числа в итерированной базе 2: a Num имеет (возможно, пустой) список разных дочерних элементов x1,...,xp типа Num, так что Num([x1,...,xp]) == 2^x1 + ... + 2^xp.

Это определяет уникальный способ записи неотрицательного целого числа; не забудьте отсортировать экспоненты, чтобы сравнение имело смысл. Равенства:

2^x + 2^x == 2^(x+1) == Num([x+1])
2^x + 2^y == Num([x,y]), когда x != y
(2^2^x)^2^y == 2^2^(x+y) == Num([Num([x+y])])

вместе с ассоциативностью/коммутативностью сложения позволяют добавлять произвольные числа и вычислять x^y для чисел вида 2 ^ 2 ^ k; этот класс чисел содержит 2 (с k = 0) и закрыт при ^, поэтому это гарантирует, что каждое число, которое нам нужно манипулировать, имеет этот вид.

Кроме того, указанные выше равенства никогда не увеличивают количество узлов в дереве, поэтому все Num имеют размер O(n).

Таким образом, временная сложность на самом деле O(C * n^k), которая является квазилинейной в C (C - (n-1) -е каталонское число).

Ответ 2

Я думаю, что лучшее решение здесь включает в себя динамическое программирование, сложную концепцию для понимания, но очень эффективную, если все сделано правильно. Идея состоит в том, чтобы свести к минимуму количество раз, когда вам нужно сделать определенный расчет, вспомнив результаты вычислений, которые вы уже сделали, а затем используя эти знания, чтобы разделить проблему на подмножество более простых проблем.

Например, в примере 2 ^ (2 ^ 2) = (2 ^ 2) ^ 2 мы можем теперь вспомнить это как две вещи, которые эквивалентны значению 16. Так что теперь, когда мы видим, что это до 2 ^ (2 ^ (2 ^ 2)) = 2 ^ ((2 ^ 2) ^ 2), мы можем очень быстро определить каждый из них как 2 ^ 16, сделать расчет один раз, и теперь мы имеем два новых уравнения: добавьте в список значений, которые нам больше не нужно вычислять.

Это может показаться мало чем способным помочь, однако, когда у вас заканчивается очень длинная серия вопросов в круглых скобках, с еще более длинными наборами эквивалентов, это сэкономит вам время и сложность в очень длинных вычислениях для компьютер для работы на очень больших количествах. Псевдокод ниже, я appologize, это действительно широкий код psuedo, эта проблема довольно грубая, поэтому я не хотел выписывать весь алгоритм. Просто более подробно изложил концепцию

 sortedEquivalencyVector;  //Sorted greatest first, so we are more likely to se longest matches

 function(expression)

    if(portion of expression exists)  //Remember, you can only do this from the end of the expression in toward the middle!
         replace value at end of expression that matches with its already computed value

    if(simplified version exists in vector) add original expression to vector
    else compute value and add it to the vector
 end

Ответ 3

Один подход, который намного лучше, чем грубая сила (но, по общему признанию, еще дорогая), заключается в использовании концепции "стандартной формы" в первой связанной бумаге. Учитывая n, сгенерируйте каждую стандартную форму степени n, оцените ее и сохраните все значения в наборе. В конце проверьте размер набора.

Грамматика для стандартной формы

S -> (2 ^ P)
P -> (S * P)
P -> S
S -> 2

Вы начинаете с S, и в конце вы должны иметь терминалы n (т.е. 2 s).