如何在Python中判断超大整数是否为3的幂？

问题背景 #

需要判断给定的正整数N是否为3的幂（即存在非负整数x使得3^{x=N），N最多可达10}7位数字。原尝试通过对数计算判断，但存在超大整数的精度问题，原代码如下：

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. 针对超大值的高效判断方法 #

超大数字（10^7位）直接转整数计算对数会触发精度丢失，更高效可靠的思路是先通过数字特征快速过滤，再用范围估算+快速幂验证：

• 第一步：快速过滤非候选值
  • 若N是0或负数，直接返回-1；
  • 3的幂的末尾数字只能是1、3、7、9（循环周期4：3^1=3，32=9，3^3=27，34=81），不符合直接排除；
  • 3的幂的各位数字之和必为3的倍数，不符合直接排除。
• 第二步：估算x的范围
  3^x的位数k满足 k = floor(x*log10(3)) + 1，因此x的大致范围是 floor((k-1)/log10(3)) 到 floor(k/log10(3))，这个范围非常小（比如10^7位的数，x约为23025850左右，范围误差不超过2）。
• 第三步：快速幂验证
  在估算的x范围内计算3^x，和输入的数字字符串对比即可，无需处理整个超大整数的对数计算。

2. 超大整数对数的精度问题处理 #

Python的math.log10基于双精度浮点数实现，仅能保留15-17位有效数字，当N超过1e16后，对数计算会丢失低位精度，导致判断错误。解决方法：

• 放弃直接对超大整数计算对数，改用字符串特征估算：对于字符串形式的N，长度为k，首几位数字为d（比如前3位），则log10(N) ≈ (k-1) + log10(d)，这个近似值足够用来估算x的范围，精度完全满足需求。
• 彻底避开对数计算：直接用字符串长度结合3的幂的位数规律，估算x的可能值，再用快速幂验证，从根源上避免精度问题。

3. 其他实现方法 #

方法一：字符串模拟快速幂验证

针对无法直接转成整数的超大规模数字（10^7位），可以用字符串模拟乘法实现快速幂，避免内存过载：

import math

def is_power_of_three_large(num_str):
    # 处理边界情况
    if num_str.startswith('-') or num_str == '0':
        return -1
    # 去除前导零
    num_str = num_str.lstrip('0')
    if not num_str:
        return -1
    if num_str == '1':
        return 0  # 3^0=1
    
    # 字符串乘法：将字符串数字乘以3
    def multiply_by_three(s):
        result = []
        carry = 0
        for c in reversed(s):
            digit = int(c)
            product = digit * 3 + carry
            result.append(str(product % 10))
            carry = product // 10
        while carry > 0:
            result.append(str(carry % 10))
            carry = carry // 10
        return ''.join(reversed(result))
    
    # 估算x的最大可能值
    log10_3 = math.log10(3)
    max_x = int(len(num_str) / log10_3) + 2
    current = '1'
    x = 0
    
    while len(current) < len(num_str):
        current = multiply_by_three(current)
        x += 1
    
    while len(current) <= len(num_str) and x <= max_x:
        if current == num_str:
            return x
        current = multiply_by_three(current)
        x += 1
    
    return -1

# 示例使用
n_str = input("Enter a number: ")
print(is_power_of_three_large(n_str))

方法二：模运算+范围验证

结合模运算特征进一步缩小验证范围，利用Python原生支持任意长度大整数的特性实现：

import math

def is_power_of_three_bigint(num_str):
    if num_str.startswith('-') or num_str == '0':
        return -1
    num_str = num_str.lstrip('0')
    if not num_str:
        return -1
    if num_str == '1':
        return 0
    
    # 快速过滤
    last_digit = num_str[-1]
    if last_digit not in {'1','3','7','9'}:
        return -1
    digit_sum = sum(int(c) for c in num_str)
    if digit_sum % 3 != 0:
        return -1
    
    # 估算x范围
    log10_3 = math.log10(3)
    min_x = int((len(num_str)-1)/log10_3)
    max_x = int(len(num_str)/log10_3) + 1
    
    for x in range(min_x, max_x+1):
        power = str(3**x)
        if power == num_str:
            return x
    return -1

内容的提问来源于stack exchange，提问作者Adel