我试图确定给定的正整数 ( N ) 是否为 3 的幂，即是否存在非负整数 ( x ) 使得 ( 3^x = N )。挑战在于 ( N ) 可能非常大，最多有 ( 10^7 ) 位数字。

这是我想要实现的逻辑：

  1. 如果（N）小于或等于0，则返回-1。
  2. 使用对数计算确定 ( N ) 是否是 3 的幂。
  3. 如果它是 3 的幂，则打印 (x) 的值；否则，打印 -1。

我已经尝试了以下代码，但我担心大整数的精度问题：

import math

def is_power_of_three(N):
    if N <= 0:
        return -1
    log3_N = math.log10(N) / math.log10(3)
    if abs(log3_N - round(log3_N)) < 1e-10:
        return int(round(log3_N))
    else:
        return -1

# Example usage:
N = int(input("Enter a number: "))
print(is_power_of_three(N))

问题：

  1. 有没有更有效的方法来检查（N）是否是3的幂，特别是对于非常大的值？
  2. 在计算如此大的整数的对数时，如何处理 Python 中的精度问题？
  3. 是否有其他方法可以实现同样的目标？

10

  • 1
    您是否需要查明它是否是其中之一或者它是哪一个？


    – 


  • 网上有地方可以让我们尝试一下吗？


    – 

  • 您询问的是给定的 N，在您的代码中它是一个 int。这真的是任务吗？或者真正给出的是一个字符串（正如您的示例用法所暗示的那样）？


    – 


  • 问题 1 没有多大意义… 要求比错误更有效的东西。答案几乎是“不”，但那只是因为你的错误速度非常快。


    – 


  • 1
    @lastchance 这有多大帮助？


    – 


最佳答案
4

任何涉及重复除法的方法在处理如此大的数字时都会很慢。

相反，考虑使用数字的位长度（实际上是其以 2 为底的对数的上限）来近似相应的 3 的幂，然后检查它是否确实相等：

import math
def what_power_of_3(n):
    if n <= 0:
        return -1
    k = math.floor(n.bit_length() * (math.log(2) / math.log(3)))
    if n == 3**k:
        return k
    else:
        return -1

这很快：测试只需要一次指数运算，因此对于例如 3**10000000，在我的智能手机上只需要几秒钟。

简单概括一下为什么这是正确的：

由于相等性检查，如果n不是 3 的幂，则答案将始终正确（因为n == 3**k不可能为真）。因此，足以证明k当 时，此答案始终正确n == 3 ** k。设k > 0，n = 3 ** k，和t = n.bit_length()。然后，3 ** k < 2 ** t < 3 ** (k + 1)根据 的定义bit_length()。因此k < t * log(2) / log(3) < k + 1，因此n.bit_length() * (math.log(2) / math.log(3))将是严格k介于和之间的分数值k+1；因此，floor该值的 恰好是k。

15

  • 2
    哦天哪，在我的桌面上只需要 0.02 秒。你赢了，回答得好


    – 


  • 非常优雅，并且能及时返回问题所要求的值。我大约在一秒钟内就完成了 3**1000000。


    – 

  • 问题1：为什么不呢k = math.floor(math.log(n, 3))？


    – 


  • 1
    谢谢。从数学上看，这看起来不错。但对于浮点数，我仍然不太确定。


    – 

  • 3
    我刚刚重读了这个问题：它已经用过了round(log3_N))。你建议用别的东西代替……我想你应该说说为什么你的更好。


    – 

您的函数应该返回布尔值。返回“标记值”-1似乎很奇怪，而且不符合习惯用法。

使用对数的另一种方法是使用重复除法。因为我们要除以底数，所以运行时间复杂度是对数的（但对于非常大的数字来说更糟糕）。

def is_power_of(n, d):
    if n == 1: return True
    if n < d: return False
    while n >= d:
        if n % d: return False
        if n == d: return True
        n //= d
    return False

现在，如果您需要知道数字是三的哪个-1幂，这就是您返回的原因，那么我仍然建议您不要返回-1而是None。并且使用不同的函数名称。

def power_of(n, d):
    if n == 1: return 0
    if n < d: return None
    exp = 1
    while n >= d:
        if n % d: return None
        if n == d: return exp
        exp += 1
        n //= d
    return None

0

要检查数字n的幂p，可以将该数字转换为底数p，然后检查第一位数字（左边）是否为 1，其余数字是否为 0。

x = 3**100000
y = x - 1
z = x - 9
a = 30

def ternary (n):
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = divmod(n, 3)
        nums.append(str(r))
    return ''.join(reversed(nums))

def is_power_of_3(n):
    nstr = ternary(n)
    return nstr[0] == '1' and '1' not in nstr[1:] and '2' not in nstr[1:]

print("x = {}\ny = {}\nz = {}\na = {}".format(is_power_of_3(x), is_power_of_3(y), is_power_of_3(z), is_power_of_3(a)))

我举了4个例子，只不过x是3的幂。

输出：

x = True
y = False
z = False
a = False

real    2.60s
user    2.59s
sys     0.01s
cpu     99%

仅需测试一个值：

x = True

real    0.88s
user    0.87s
sys     0.01s
cpu     99%

这在速度上不会与 nneonneo 匹敌。然而，它试图完全保持在整数运算范围内，尽管需要 O(log(N)) 次除法。

需要注意的一点是：如果你取一个很大的数字，那么很有可能它不是 3 的幂。因此，你应该尽快排除：可能在将输入字符串转换为整数之前。

3 的任何幂的形式为 3**(4k+m)，其中 m 为 0、1、2 或 3。m 每个值对应的最后一位数字为 1、3、9 或 7。任何其他数字结尾都会被立即拒绝。

如果以 1 结尾，则检查 x 是否是 3**4 的幂，即 81

如果以 3 结尾，则检查 x 是否能被 3 整除以及 x/3 是否是 81 的幂。

如果以 9 结尾，则检查 x 是否能被 9 整除以及 x/9 是否是 81 的幂。

如果以 7 结尾，则检查 x 是否能被 27 整除，并且 x/27 是否是 81 的幂。

因此，除了初始检查之外，您还要询问某个数是否是 81 的幂。此外，81 的每个幂都以数字 1 结尾。

然后，一个数字可能是给定数字的偶数幂或奇数幂。因此，对于新的测试数字 y，检查 y 或 y/81 是否是 81 的幂。然后您将递归，测试 81、81^2、81^4、81^8 等的幂。

def test( n, x ):                      # n is 81, 81^2, 81^4, 81^8 etc.
    if x == 1 or x == n: return True
    if x % 10 != 1: return False
    if x % n  != 0: return False
    nsq = n * n
    return test( nsq, x ) or test( nsq, x // n )


def isPowerOf3( x ):
    lastDigit = x % 10
    if lastDigit == 1: 
       return test( 81, x )
    elif lastDigit == 7 and x % 27 == 0:
       return test( 81, x // 27 )
    elif lastDigit == 9 and x % 9 == 0:
       return test( 81, x // 9 )
    elif lastDigit == 3 and x % 3 == 0:
       return test( 81, x // 3 )
    return False


for i in range( 10000000 ):
    if ( isPowerOf3( i ) ): print( i )
    
print( isPowerOf3( 3**100000     ) )
print( isPowerOf3( 3**100000 + 1 ) )

是的，倒数第二个测试需要几秒钟：

1
3
9
27
81
243
729
2187
6561
19683
59049
177147
531441
1594323
4782969
True
False