5 Best Ways to Check for Prime Number of Set Bits in Binary Representation in Python

💡 Problem Formulation: How can one determine if a given positive integer has a prime number of ‘set bits’ (bits that are ‘1’) in its binary representation? For instance, if the input is 5 (which is 101 in binary), the desired output is True since it contains two set bits and two is a prime number.

Method 1: Using a Simple Iterative Function

This method includes defining a function that counts the number of set bits by checking each bit individually, calculates the sum, and then checks if the sum is a prime number. The prime check is performed by another function that iterates through possible divisors.

Here’s an example:

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def count_set_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def is_prime_set_bits(num):
    return is_prime(count_set_bits(num))

print(is_prime_set_bits(5))

Output:

True

This example defines two functions where count_set_bits() counts the number of 1 bits by shifting the input number to the right until it becomes 0, incrementing the count whenever the least significant bit is 1. The is_prime_set_bits() function then uses the is_prime() helper function to determine if the count is a prime number.

Method 2: Using the Built-in bin() Function and a Set for Prime Checking

In this method, a common Python built-in function bin() is used to convert the number to a binary string. The count of ‘1’s is then found by counting the occurrences in the string. A pre-defined set of prime numbers up to a certain limit is used for prime checking, to avoid recomputation.

Here’s an example:

primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

def is_prime_set_bits_bin(num):
    return bin(num).count('1') in primes

print(is_prime_set_bits_bin(5))

Output:

True

The function is_prime_set_bits_bin() counts the number of set bits using bin() and string count method, then checks if this count is a member of the primes set. This method is efficient because it avoids re-checking for prime numbers.

Method 3: Using Bitwise Operations with Memoization

This method optimizes prime checks by storing previously computed prime results (memoization). Bitwise operations are used for set bit counting, and a dictionary is used to store prime checking results to reduce computation for repeated counts.

Here’s an example:

def is_prime_memo(num, memo={}):
    if num in memo:
        return memo[num]
    
    if num < 2:
        memo[num] = False
        return False
    
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            memo[num] = False
            return False
    
    memo[num] = True
    return True

def is_prime_set_bits_memo(num):
    return is_prime_memo(bin(num).count('1'))

print(is_prime_set_bits_memo(5))

Output:

True

The is_prime_memo() function takes advantage of memoization by storing previously determined prime statuses in a dictionary, significantly speeding up the process in cases with repetitive counts. The main function is_prime_set_bits_memo() leverages this for efficient prime checking.

Method 4: Using List Comprehension and Sieve of Eratosthenes

Method 4 uses the Sieve of Eratosthenes algorithm to precalculate a list of prime numbers and list comprehension to count set bits. This technique is efficient as it reduces the time complexity of prime number generation.

Here’s an example:

def generate_primes(n):
    sieve = [True] * n
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            sieve[i*i:n:i] = [False] * len(sieve[i*i:n:i])
    return [i for i in range(2, n) if sieve[i]]

primes = set(generate_primes(256))

def is_prime_set_bits_sieve(num):
    return bin(num).count('1') in primes

print(is_prime_set_bits_sieve(5))

Output:

True

The generate_primes() function generates all prime numbers up to a set maximum (256 in this case, as this is sufficient for the set bit range in a typical integer). This list of prime numbers is then converted to a set called primes for efficient lookup. The main function is_prime_set_bits_sieve() uses this prime numbers set for checking.

Bonus One-Liner Method 5: Utilizing List Comprehension and the all() Function

This concise one-liner leverages Python’s expressive list comprehensions and the all() function. The all() function is used within a list comprehension to determine if the number of set bits is prime.

Here’s an example:

is_prime_set_bits_one_liner = lambda num: bin(num).count('1') > 1 and all(bin(num).count('1') % i != 0 for i in range(2, bin(num).count('1')))

print(is_prime_set_bits_one_liner(5))

Output:

True

This lambda function checks if the count of set bits is more than one and then if it is not divisible by any number less than itself, excluding 1, using a generator expression within the all() function. This is a compact but less efficient solution as it doesn’t use memoization or a precalculated set of primes.

Summary/Discussion

• Method 1: Iterative Prime Checking. Strengths: Simple and straightforward logic. Weaknesses: Not as efficient as using precalculated prime sets or memoization.
• Method 2: bin() with Prime Set. Strengths: Fast and efficient for small set bit counts with precalculated primes. Weaknesses: Limited by the size of the precalculated prime set.
• Method 3: Bitwise with Memoization. Strengths: Reduces repeated calculations with memoization technique. Weaknesses: Requires additional space for the memoization dictionary.
• Method 4: Sieve of Eratosthenes. Strengths: Highly efficient for generating prime numbers, making it suitable for large inputs. Weaknesses: Overhead of sieve generation for small inputs.
• Method 5: One-Liner List Comprehension. Strengths: Very short and readable. Weaknesses: Poor performance due to lack of optimization techniques.