OEIS A002845：2的n个幂次方（插入所有可能方式的括号）所取得的不同值的数量

Question

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

让^表示指数运算符。考虑形如2^2^...^2的表达式，其中有n个2并插入所有可能的括号（可能的括号数由Catalan numbers给出）。其中一些表达式将具有相同的值，例如(2^2)^2=2^(2^2)。我们对于给定的n感兴趣的是不同值的数量。

显然，可以通过直接计算这些表达式来找到一个明显的暴力解决方案，但很明显，所需的时间和空间很快就会超出所有合理限制，即使对于相对较小的n也是如此。我对这个问题的多项式时间解决方案感兴趣。

- Vladimir Reshetnikov

---

这里有一个与之相关的问题在MO上：http://mathoverflow.net/questions/103411/number-of-distinct-values-taken-by-alpha-alpha-dots-alpha-with - Vladimir Reshetnikov

你读过链接的论文吗？http://www.jstor.org/stable/2316312?seq=1 和 http://www.jstor.org/stable/10.2307/2319392。虽然我只是浏览了一下，但前者展示了一些基于树的东西与某些相等关系，可能会有帮助。 - Danica

在MO上有一个相关的问题：http://mathoverflow.net/questions/79442/ - user149341

@Vlad: (2^2)^(2^2) = ((2^2)^2)^2@Vlad：（2的平方）的四次方 = （（2的平方）的平方）的平方 - Vladimir Reshetnikov

免费获取论文副本（并非所有人都有JSTOR）http://oeis.org/A003018/a003018.pdf - Colonel Panic

Answer 1

只需将数字以迭代的二进制表示：一个Num具有类型为Num的（可能为空的）不同子节点x1，...，xp的列表，因此Num([x1，...，xp]) == 2 ^ x1 + ... + 2 ^ xp。

这定义了一种唯一的写非负整数的方式；记得对指数进行排序，以便比较有意义。等式：

- 2 ^ x + 2 ^ x == 2 ^（x + 1）== Num（[x + 1]） - 当x！= y时，2 ^ x + 2 ^ y == Num（[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数）中准线性。

- Generic Human

---

我认为这个答案最接近问题的解决方案。我很高兴将悬赏奖励授予它的作者。 - Vladimir Reshetnikov

Answer 2

我认为最好的解决方案涉及到动态规划，这是一个难以理解的概念，但如果正确执行非常有效。其想法是通过记住已经完成的计算结果，尽量减少进行某些计算的次数，然后利用这些知识将问题分成一组更简单的子问题。

例如，在您的2^(2^2) = (2^2)^2例子中，我们现在可以将其记为等于16的两个事物。因此，当我们看到它附加到2^(2^(2^2)) = 2^((2^2)^2)时，我们可以很快地将每个都识别为2 ^ 16，进行一次计算，然后我们现在有两个新方程式添加到我们永远不必再计算的值列表中。

虽然这可能似乎没有什么帮助，但当你最终得到一长串括号内的问题以及更长的等价集时，这将节省大量时间和复杂性，而这对于计算机处理非常大的数字来说是非常漫长的计算。下面是伪代码，我很抱歉，这是非常宽泛的伪代码，这个问题相当棘手，所以我不想写出整个算法。只是更详细地概述了这个概念。

 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

- MobA11y

---

即使不进行重新计算，这些值也会快速增长 - 即使只计算一次这样的值，也需要大量的时间和内存。 - Zakharia Stanley

是的，但仅仅因为一个问题很难并不意味着它是可以避免的... 思路是尽量将长时间计算的数量减少到最小。如果你有一个完全避免这些计算的答案，为什么不提供呢？ - MobA11y

我没有答案，也不会声称我有。但你的帖子也不是一个答案。你只是给出了一些显而易见的建议，这些建议已经在评论中提到过，它们无助于解决主要的障碍 - 数量巨大。没有针对个人的意思，但我认为这个问题非常有趣，值得一个真正的答案。 - Zakharia Stanley

我完全不同意。这个问题不是关于计算2^2^2^2^2^2的值，而是关于计算所有括号组合的复杂度问题。其中一个是针对堆栈溢出的算法问题，另一个是数学问题，这并不是问题所关注的“我对这个问题感兴趣，希望能够找到一个多项式时间解决方案。”这表明他更关心整体解决方案的大O复杂度，而不是简化一个实例的计算。 - MobA11y

我猜，总的来说，我的解决方案是这个板块上最好的。如果它在计算上太复杂而无法实现，它不一定值得被“接受”，但它仍然在理论上是正确的，不应该被点踩。 - MobA11y

有用的想法，但不幸的是，这并不是一个答案。它不能直接用于计算所讨论的序列。 - Oksana Gimmel

Answer 3

一种比暴力搜索更好的方法（尽管仍然很耗费资源）是使用第一个链接论文中的“标准形式”概念。给定一个 n，生成每个度数为 n 的标准形式，进行评估，并将所有值保存在一个集合中。最后，检查集合的大小。

标准形式的语法如下：

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

你从一个 S 开始，最终应该有 n 个终端（即 2）。

- mitchus