algorithm - 按顺序生成数字(幂)序列

Question

我正在寻找一种算法(或者更好的是，代码!)来生成幂，特别是奇数指数大于 1 的数字:三次幂、五次幂、七次幂等等。然后我想要的输出是

8, 27, 32, 125, 128, 216, 243, 343, 512, 1000

依此类推，直到指定的限制。

我不想将幂存储在一个列表中并对它们进行排序，因为我做的太多以至于内存无法容纳——希望这个限制是 10³⁰ 左右，对应于≈ 1 TB 的内存需求。

我的基本想法是用一个数组保存每个指数的当前数字(从 2 开始)，从 3 开始一直到极限的二进制对数。在每个步骤中，我循环遍历指数数组，找到产生最小功率的那个(找到 pow(base, exponent) 或更可能的 exponent * log(base)，可能会记住这些值)。那时调用“输出”函数，它实际上会用数字进行计算，但当然你不需要担心这个。

当然，由于所涉及的数字范围，必须使用 bignums -- 内置在语言中、库中或自行滚动。相关代码或代码片段将不胜感激:我觉得这个任务类似于一些经典问题(例如，Hamming's problem of generating numbers that are of the form 2^x3^y5^z) 并且可以有效地求解。我在这里完全与语言无关:我的“输出”函数只需要数组、减法、bignum 字比较和 bignum 整数平方根函数。

Answer 1

您的示例缺少 64=4^3 和 729=9^3。

您想要按数字顺序遍历的所有 { n^m } 的集合，m 奇数，n 积分和 n > 1。我们知道(对于 n > 1)增加 n 或 m 会增加这个值，但缺乏计算我们无法比较其他。

有两种明显的“双重”方法可以做到这一点:跟踪您考虑的最高基数 n，对于所有小于它的基数，下一个要考虑的指数 m。然后选择最小的一个，并将其与 n^3 进行比较。或者，反过来 - 跟踪最高指数 m，对于小于该指数的每个指数，跟踪使用的最高基数，并找到最小的基数，并将其与添加 2^m 进行比较。

为了有效地跟踪这些数字，您需要将它们保存在 priority queue 中。 .现在，您仍然希望一次最小化优先级队列中的条目数，因此我们需要弄清楚这两种方法中哪一种在这方面做得更好。事实证明，要达到给定点，需要更高的 n 值。在数字 k 处，看到的 m 的最大值将是 k 的 log_2，而看到的 n 的最大值将是 k^(1/3)。

因此，我们有一个包含元素 (v, n, m) 的优先级队列，其中值 v=n^m。

add_priority_queue(2^3, 2, 3)
for m in 5, 7, ....
    v = 2^m
    while value(peek(queue)) <= v:
        (v1, n1, m1) = pop(queue)
        if v1 != v print v1
        add_priority_queue((n1+1)^m1, n1+1, m1)
    add_priority_queue(2^m, 2, m)

请注意，我们需要检查 v1 = v:我们可以有 2^9 = 512 = 8^3，并且应该只打印一个，对吗？

Haskell 实现，带有从 hackage 中获取的随机优先级队列.

import Data.MeldableHeap

dropMin q = maybe empty snd (extractMin q)

numbers = generate_values (insert (2^3, 2, 3) empty) 5

generate_values q m = case findMin q of
    Nothing -> []
    Just (v1, n1, m1) -> case compare v1 (2^m) of
        EQ -> generate_values (insert ((n1+1)^m1, n1+1, m1) (dropMin q)) m
        LT -> v1 : generate_values (insert ((n1+1)^m1, n1+1, m1) (dropMin q)) m
        GT -> 2^m : generate_values (insert (3^m, 3, m) q) (m + 2)

main = sequence_ (map print numbers)

8 分钟后，我目前在 177403008736354688547625(即 23 位数字)和 1.3 GB 明文输出中运行