algorithm - OEIS A002845 : Number of distinct values taken by 2^2^. ..^2(以所有可能的方式插入 n 个 2 和括号)

Question

我正在寻找一种相当快速的算法来计算 OEIS 序列的项 A002845 .让我在这里重申它的定义。

令 ^ 表示求幂运算符。考虑 2^2^...^2 形式的表达式，其中 n 个 2's 以所有可能的方式插入括号(可能的括号数由 Catalan numbers 给出)。其中一些表达式将具有相同的值，例如 (2^2)^2=2^(2^2)。我们对给定 n 的不同值的数量感兴趣。

通过直接计算这些表达式，有一个明显的蛮力解决方案，但很明显，即使对于相对较小的 n，所需的时间和空间也很快超过了所有合理的限制。我对这个问题的多项式时间解很感兴趣。

Answer 1

仅表示以 2 为基数的迭代数字: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])])

连同加法的结合律/交换律，您可以添加任意数字并为 2^2^k 形式的数字计算 x^y；此类数字包含 2(k=0)并在 ^ 下关闭，因此这保证了我们需要处理的每个数字都是这种形式。

此外，上面定义的等式不会增加树中节点的数量，因此所有 Num 的大小都是 O(n)。

所以时间复杂度实际上是 O(C * n^k) 这在 C 中是准线性的(C 是第 (n-1) 个 Catalan 数)。