How to determine if a large integer is a power of 3 in Python?

I'm trying to determine if a given positive integer ( N ) is a power of 3, i.e., if there exists a nonnegative integer ( x ) such that ( 3^x = N ). The challenge is that ( N ) can be extremely large, with up to ( 10^7 ) digits.

Here's the logic I want to implement:

If ( N ) is less than or equal to 0, return -1.
Use logarithmic calculations to determine if ( N ) is a power of 3.
If it is a power of 3, print the value of ( x ); otherwise, print -1.

I've tried the following code, but I'm concerned about precision issues with large integers:

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))

Question:

Is there a more efficient way to check if ( N ) is a power of 3, especially for very large values?
How can I handle precision issues in Python when calculating logarithms for such large integers?
Are there alternative methods to achieve the same goal?

Solution

Any approach that involves repeated division is going to be slow with numbers that large.

Instead, consider using the bit length of the number (effectively the ceiling of its base 2 logarithm) to approximate the corresponding power of three, then check to see if it is indeed equal:

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

This is fast: the test requires only a single exponentiation, so for e.g. 3**10000000, it requires only a few seconds on my smartphone.

A brief sketch to show why this is correct:

Because of the equality check, if n is not a power of 3, the answer will always be correct (because n == 3**k cannot be true). So it suffices to prove that this answer always finds the correct k when n == 3 ** k. Let k > 0, n = 3 ** k, and t = n.bit_length(). Then, 3 ** k < 2 ** t < 3 ** (k + 1) by definition of bit_length(). Thus k < t * log(2) / log(3) < k + 1, and so n.bit_length() * (math.log(2) / math.log(3)) is going to be a fractional value that lies strictly between k and k+1; thus, the floor of that value will be exactly k.