检查一个数是否是另一个数的完全幂

Question

例如，243是3的一个完全幂，因为243=3^5。

我之前一直使用(math.log(a) / math.log(b)).is_integer()，我认为它工作得很好，但是当我尝试上面的例子时，由于浮点数运算，它实际上返回了4.999999999999999。所以我发现只有在非常小的数字（小于100左右）才可靠。

我想我可以使用循环来进行重复的乘法...即将i设置为3，然后9，27，81，243，等于目标，所以我们知道它是完全幂。如果它超过了243，那么我们就知道它不是一个完全的幂。但是我已经在循环中运行了这个检查，所以这似乎非常低效。

那么，除此之外，是否还有其他可靠的方法来检查一个数字是否是另一个数字的完全幂呢？

- clb

---

请参考此链接：http://cstheory.stackexchange.com/questions/2077/how-to-check-if-a-number-is-a-perfect-power-in-polynomial-time - Sven Marnach

关于 XY 问题中的 Y：不要使用相等性测试来测试浮点数，而是测试它们的接近程度（例如检查 math.log(a) / math.log(b) 是否接近其整数部分）。 - Andras Deak -- Слава Україні

请注意，我发布的链接涵盖了您想要检测一个数字是否是任何其他数字的非平凡完全幂的情况，例如，您不知道b。 - Sven Marnach

相关链接：https://dev59.com/3WUp5IYBdhLWcg3wRV9D - wim

你已经知道 b=3 了吗，还是也在尝试寻找它？ - Teepeemm

Answer 1

尝试：

b ** int(round(math.log(a, b))) == a

也就是说，只使用log()（注意有两个参数的形式！）来猜测一个整数幂，然后验证“是否有效”。请注意，即使是作为浮点数无法表示的大整数参数，math.log()也会返回合理的结果。还请注意，Python中的整数**是精确的，并且在内部使用高效的算法（进行与指数位数成比例的多次乘法）。总之，这种方法简单直接，而且通常比重复除法更加高效。但如果你有其他问题，请参考其他回答。

- Tim Peters

---

值得注意的是，虽然这个解决方案对于大数值并不完全可靠，因为它依赖于浮点精度，但是a必须非常大才会出现问题。例如，当b=2，a=2 **（2 ** 53 + 1）和IEEE 754浮点数时，这显然行不通，但是你需要大约1.2 PB的RAM和一个地址空间大于2 ** 48的机器才能够在第一时间表示出a的值。 - Mark Dickinson

是的，目前不存在任何一台计算机具有足够的内存来存储足够大的整数以使其可能失败。但我没有提到这一点，因为如果问题提出者对于log()在某些情况下可能不精确感到惊讶，他们还没有准备好欣赏关于理论可能性的遥远极限的论证;-) - Tim Peters

谢谢！知道你也可以将基数作为第二个参数传递是很有帮助的。:) 但是，当round()返回一个整数时，int()是否必要呢？ - clb

必要的，是的！需要使用int()函数，这样指数运算才能将整数提高到整数幂，从而得到精确计算。如果没有int()函数，我们将会把一个整数提高到浮点数幂，这只是一个近似值。顺便说一下，Python 2和3中1个参数的round()函数的行为是不同的。在Python 3中不需要int()函数，但也无妨，而在Python 2中则是必需的。 - Tim Peters

好的，我之前只用过Python 3，所以不知道在Python 2中round()实际上返回一个浮点数。 - clb

在这里Py3可能会让人感到困惑；例如round(12.3)是int12，但是round(12.3, -1)是float10.0。在Py2中，round()总是返回一个float。无论如何，如果您的问题得到了回答，您应该接受答案：http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work - Tim Peters

Answer 2

也许可以这样表述：

def is_perfect_power(a, b):
  while a % b == 0:
    a = a / b
  if a == 1:
    return True
  return False

print is_perfect_power(8,2)

- Abd Azrad

Answer 3

您可以使用sympy的perfect_power：

>>> from sympy import perfect_power
>>> perfect_power(243)
(3, 5)
>>> perfect_power(244)
False

如果你只是想检查给定数字是否是某个给定底数的完全幂，请查看下面@smichr的评论。

- Sadeq Dousti

---

如果你不知道底数，就可以使用这个。在这种情况下，似乎用户知道底数是3，例如 sympy.core.power.integer_log(243, 3) -> (5, True) ，它使用了@samgak建议的方法。 - smichr

@smichr：好的，我修改我的回答，指向你的评论。 - Sadeq Dousti

Answer 4

如果你需要处理大量的数字，你可能需要查看gmpy2。gmpy2提供了访问GMP多精度库的接口。其中一个提供的函数是is_power()。它将返回True，如果参数是某个基数数的完全幂。它不会提供幂或基数，但它可以快速过滤掉不能成为完美幂的数字。

>>> import gmpy2
>>> [n for n in range(1,1000) if gmpy2.is_power(n)]
[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961]

一旦您确定可能的幂，就可以使用iroot_rem(x,n)查找x的第n次根和余数。然后，一旦您找到有效的指数，就可以找到底数。以下是一个示例，它在范围内搜索所有可能的完全幂。

>>> for x in range(1,1000):
...   if gmpy2.is_power(x):
...     for e in range(x.bit_length(), 1, -1):
...       temp_root, temp_rem = gmpy2.iroot_rem(x, e)
...       if not temp_rem:
...         print x, temp_root, e
... 
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
<< remainder clipped>>

免责声明：我维护 gmpy2。

- casevh

Answer 5

如果您想加速大数的重复除法，可以制作一个以基数为底数的指数的列表，其中指数是2的幂，并仅测试这些指数。

例如，取3的9次方。 9在二进制中是101，即2的3次方+2的1次方=8 + 1。

因此，3的9次方=3的8 + 1次方=3的2的3次方+2的1次方=3的2的3次方 x 3的2的1次方

您只需要进行两次试除，而不是9次。

def is_power(a, b):
  if b == 0 or b == 1:
    return a == b
  if a < b:
    return False
  c = []
  # make a list of the power of 2 exponents less than or equal to a:
  while b * b <= a:
    c.append(b) 
    b = b * b
  # test against each of them where b <= remaining a:
  while True: 
    if a % b != 0:
       return False
    a //= b
    while b > a:
      if len(c) == 0:
        return a == 1
      b = c.pop()
  return True

适用于正整数，例如：

print is_power(3**554756,3)
print is_power((3**554756)-1,3)

输出：

True
False

- samgak

Answer 6

def checkifanumberisapowerofanothernumber(x,y):
    if x==1:
        return y==1
    p=1
    while p<y:
        p=p*x
    return p==y

这将重复计算x的幂，直到数字接近y。然后检查数字是否等于y。

- ravi tanwar

Answer 7

如果基数和指数都是通配符，并且您只有“大数字”结果，那么您将面临速度和内存的权衡。由于您似乎暗示嵌套循环会“低效”，我假设CPU周期效率对您很重要。在这种情况下，我建议预先计算一堆基数-指数对：一种彩虹表，如果您愿意的话。这将消耗更多的内存，但CPU周期要少得多。然后，您可以简单地迭代您的表格并查看是否找到匹配项。或者，如果您非常关心速度，甚至可以对表进行排序并进行二进制搜索。您甚至可以将预先计算的表存储在文件中，如果您喜欢的话。

此外，您没有指定您只想要一个是/否答案，还是您正在尝试找到幂的相应基数和指数。因此，我假设您想找到一个基数-指数对（某些完全幂将具有多个基数-指数解决方案）。

试试这个（我使用Python 3）：

#Setup the table as a list
min_base = 2 #Smallest possible base
max_base = 100 #Largest possible base
min_exp = 2 #Smallest possible exponent
max_exp = 10 #Largest possible exponent
powers = []

#Pre-compute the table - this takes time, but only needs to be done once
for i in range(min_base, max_base+1):
    for j in range(min_exp, max_exp+1):
        powers.append([i, j, i ** j])

#Now sort the table by the 3'rd element - again this is done only once
powers.sort(key=lambda x: x[2])


#Binary search the table to check if a number is a perfect power
def is_perfect_power(a, powers_arr):
    lower = 0
    upper = len(powers_arr)
    while lower < upper:
        x = lower + (upper - lower) // 2
        val = powers_arr[x][2] #[2] for the pre-computed power
        if a == val:
            return powers_arr[x][0:2]
        elif a > val:
            if lower == x:
                break
            lower = x
        elif a < val:
            upper = x
    return False #Number supplied is not a perfect power

#A simple demonstration
print(is_perfect_power(243, powers)) #Output is [3, 5]
print(is_perfect_power(105413504, powers)) #Output is [14, 7]
print(is_perfect_power(468209, powers)) #Output is False - not a perfect power

数学方面更有天赋的人可能会有更高效的答案，但这应该能帮助你入门。在我的机器上，这个程序运行得相当快。

- Ben Hershey

---

我认为OP正在寻找一个已知的基础。 - Sven Marnach

也许吧，但考虑到他说他已经在循环中检查这些了，我假设他正在遍历某些基础。我向后退了一步，看问题的整体。也许对他没有帮助，但希望对其他人有帮助。 - Ben Hershey