使用小型优先级队列(每个幂有一个条目)是列出数字的合理方法。请参阅以下 python 代码。
import Queue # in Python 3 say: queue
pmax, vmax = 10, 150
Q=Queue.PriorityQueue(pmax)
p = 2
for e in range(2,pmax):
p *= 2
Q.put((p,2,e))
print 1,1,2
while not Q.empty():
(v, b, e) = Q.get()
if v < vmax:
print v, b, e
b += 1
Q.put((b**e, b, e))
使用上面代码中的 pmax、vmax,它会产生以下输出。对于提出的问题,替换pmax
and vmax
with 64
and 2**64
.
1 1 2
4 2 2
8 2 3
9 3 2
16 2 4
16 4 2
25 5 2
27 3 3
32 2 5
36 6 2
49 7 2
64 2 6
64 4 3
64 8 2
81 3 4
81 9 2
100 10 2
121 11 2
125 5 3
128 2 7
144 12 2
该方法的复杂度为O(vmax^0.5 * log(pmax))。这是因为完美平方的数量比完美立方、四次方等的数量占主导地位,并且对于每个正方形,我们需要 O(log(pmax)) 工作get
and put
队列操作。对于更高的幂,我们在计算时会进行 O(log(pmax)) 工作b**e
.
When vmax,pmax =64, 2**64
,大约会有 2*(2^32 + 2^21 + 2^16 + 2^12 + ...) 个队列操作,即大约 2^33 个队列操作。
添加注释:这篇文章针对 cf16 的评论,“只有一点,我不认为“完全平方数的数量比完全立方数、四次方等的数量占主导地位。”它们都是无限的。但是,是的,如果我们考虑有限集”。确实,在事物的整体数学方案中,基数是相同的。也就是说,如果P(j)
是所有的集合j
'整数的幂,然后是基数P(j) == P(k)
对于所有整数j,k > 0
。任意两组幂的元素都可以一一对应。
Nevertheless, when computing perfect powers in ascending order, no matter how many are computed, finite or not, the work of delivering squares dominates that for any other power. For any given x, the density of perfect kth powers in the region of x declines exponentially as k increases. As x increases, the density of perfect kth powers in the region of x is proportional to (x1/k)/x, hence third powers, fourth powers, etc become vanishingly rare compared to squares as x increases.
举一个具体的例子,在1e8和1e9之间的完美幂中,(2;3;4;5;6)次幂的数量约为(21622;535;77;24;10)。 1e8 和 1e9 之间的方格数量是任何比方格更高幂的实例的 30 倍多。以下是两个数字之间的完美平方数与更高完美幂数的比率:10^10–10^5,r≈301; 10^5–10^2^, r≈2K; 10²⁰–10²⁵,r≈15K; 10²⁵–10³⁰,r≈100K。简而言之,作为x当完美幂按升序传递时,平方越来越占主导地位。