5 Best Ways to Check if an Integer is a Power of 3 in Python

by

💡 Problem Formulation: Checking if a given integer n is a power of 3 in Python is a common task that can be approached in several different ways. Given an input like 9, the function should return True because 9 is 3 squared, whereas for an input like 8, the function should return False, as 8 is not a power of 3.

Method 1: Iterative Method

An intuitive method to determine if a given integer is a power of 3 is to iteratively divide the number by 3 until the result is 1 or the remainder is non-zero. This method is straightforward and can be implemented with a simple loop.

Here’s an example:

def is_power_of_three(n):
    if n < 1:
        return False
    while n % 3 == 0:
        n //= 3
    return n == 1

print(is_power_of_three(9))

Output: True

This code snippet defines a function is_power_of_three that checks if an integer n is a power of 3. If n is less than 1, it immediately returns False. Otherwise, it iteratively divides n by 3 until it cannot divide evenly anymore. If the final result is 1, it returns True; otherwise, it returns False.

Method 2: Logarithmic Check

By using logarithms, we can check if the log base 3 of an integer is an integer itself. This method involves fewer operations than iterative methods and may be faster for large integers.

Here’s an example:

import math

def is_power_of_three(n):
    if n < 1:
        return False
    # Calculate the log base 3 by dividing the logarithm of n by the logarithm of 3
    log_base3 = math.log(n, 3)
    # Check if the log_base3 is an integer by comparing it to an integer version of itself
    return math.isclose(log_base3, round(log_base3))

print(is_power_of_three(27))

Output: True

This snippet uses the math.log function to calculate the logarithm of n with base 3. It then checks if the result is an integer using the round function and comparing it with the math.isclose function. The method returns True if the two values are close enough to be considered equal, indicating n is a power of 3.

Method 3: Using Integer Limits

The maximum integer that is also a power of 3 within the 32-bit signed integer range is 3^19. We can check if the input integer is a power of three by seeing if 3^19 is divisible by it without a remainder.

Here’s an example:

def is_power_of_three(n):
    return n > 0 and (3**19) % n == 0

print(is_power_of_three(81))

Output: True

In this function, is_power_of_three, we check if n is positive and if 3**19 (3 to the power of 19) is divisible by n without any remainder. If these conditions are true, n is a power of 3.

Method 4: Recursive Check

Recursion can also be used to solve this problem by repeatedly calling the function with the input divided by 3 until the input becomes 1 or non-divisible by 3.

Here’s an example:

def is_power_of_three(n):
    return n == 1 if n < 0 else (n % 3 == 0 and is_power_of_three(n / 3))

print(is_power_of_three(243))

Output: True

This recursive implementation of is_power_of_three checks if the input n is immediately 1, indicating that the previous call was divisible by 3. If not, it checks divisibility by 3 and makes a recursive call with n divided by 3.

Bonus One-Liner Method 5: Using Set Membership

Leverage the properties of sets to check if the given integer is in a predefined set of powers of 3. This predefined set can be generated up to a certain limit to optimize the check.

Here’s an example:

powers_of_three = {3**i for i in range(20)}

def is_power_of_three(n):
    return n in powers_of_three

print(is_power_of_three(729))

Output: True

By creating a set powers_of_three that contains 3 raised to the power of numbers from 0 to 19, we have a quick way to check membership using the in keyword. This one-liner function is efficient for inputs that are within the precalculated range.

Summary/Discussion

  • Method 1: Iterative Method. Simple and easy to understand. However, it can be slower for very large numbers.
  • Method 2: Logarithmic Check. Efficient and concise. Rounding issues may cause inaccuracies with very large or small numbers.
  • Method 3: Using Integer Limits. Extremely fast but only works within certain fixed limits, like the 32-bit signed integer range.
  • Method 4: Recursive Check. Elegant and simple. Nevertheless, deep recursion can lead to stack overflow with very large numbers.
  • Method 5: Using Set Membership. Fast for numbers within a predefined range but requires memory to store the set and is limited to that range.