Summing Up Truncatable Primes Below n in Python

Rate this post

πŸ’‘ Problem Formulation: We aim to find and sum all the truncatable primes that are less than a given number, n. A truncatable prime is a prime number that remains prime when digits are truncated one at a time from either the left or right side. For instance, if n is 100, then the truncatable primes below 100 are 2, 3, 5, 7, 23, 37, 53, 73, so the desired output is their sum, which is 203.

Method 1: Brute Force with Prime Checking

The brute force method entails checking each number below n to determine if it is a truncatable prime. This involves creating a prime-checking function and then applying this function iteratively to check for prime status after consecutively removing digits from the left and right. This method is simple but not the most efficient for large values of n.

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 is_truncatable_prime(num):
    str_num = str(num)
    for i in range(len(str_num)):
        if not is_prime(int(str_num[i:])) or not is_prime(int(str_num[:i+1])):
            return False
    return True

n = 100
sum_of_truncatable_primes = sum(num for num in range(2, n) if is_truncatable_prime(num))
print(sum_of_truncatable_primes)

Output:

203

This Python code snippet defines two functions: is_prime() that checks for prime numbers, and is_truncatable_prime() that validates if a number is a truncatable prime. With these definitions, we calculate the sum of all truncatable primes below n using a list comprehension and print the result. This approach is very straightforward and easy to understand for Python beginners.

Method 2: Sieve of Eratosthenes with Truncation Check

Method 2 improves efficiency by using the Sieve of Eratosthenes algorithm to first find all prime numbers below n and then checks each prime number for truncatability. This method is particularly faster for finding primes as it reduces unnecessary computations associated with checking non-prime numbers for truncatability.

Here’s an example:

def sieve_of_eratosthenes(limit):
    sieve = [True] * limit
    sieve[0:2] = [False, False]  
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit, i):
                sieve[j] = False
    return sieve

def check_truncations(prime_str):
    return all(is_prime(int(prime_str[i:])) and is_prime(int(prime_str[:len(prime_str)-i])) for i in range(len(prime_str)))

n = 100
sieve = sieve_of_eratosthenes(n)
primes = [i for i, prime in enumerate(sieve) if prime]
sum_of_truncatable_primes = sum(filter(lambda x: check_truncations(str(x)), primes))
print(sum_of_truncatable_primes)

Output:

203

The example combines a sieve function for finding prime numbers and a truncation check function. It uses a list comprehension to generate a list of primes and then a filter function with a lambda to apply the truncation check. The sum of truncatable primes is then calculated and printed. This method is a significant improvement over brute force, especially when n is large.

Method 3: Early Termination with Prime Set

In Method 3, we further optimize by terminating the truncation check early if a non-prime truncation is found. This method uses a set to store prime numbers enabling constant time membership tests. It’s a subtle yet powerful optimization for checking truncatability.

Here’s an example:

# Re-using the sieve_of_eratosthenes from Method 2.
# Re-using is_prime from Method 1.

n = 100
sieve = sieve_of_eratosthenes(n)
primes_set = {i for i, prime in enumerate(sieve) if prime}

def is_truncatable(prime):
    for i in range(1, len(str(prime))):
        if int(str(prime)[i:]) not in primes_set or int(str(prime)[:-i]) not in primes_set:
            return False
    return True

sum_of_truncatable_primes = sum(prime for prime in primes_set if prime > 10 and is_truncatable(prime))
print(sum_of_truncatable_primes)

Output:

186

By storing the primes in a set, we benefit from constant time checks when truncating. In the code provided, the is_truncatable() function efficiently checks for truncatable primes by leveraging this set. We only consider primes greater than 10, as single-digit numbers are inherently truncatable primes. This method serves to reduce the number of required operations significantly.

Method 4: Recursive Truncation with Memoization

Method 4 introduces memoization to the truncation process, caching previous computations for faster execution. This method performs particularly well when the same truncations occur multiple times across different primes, by using a dictionary to store previously seen truncations and their prime status.

Here’s an example:

# Re-using the is_prime function from Method 1.

memoize = {}

def is_truncatable_recursive(prime):
    prime_str = str(prime)
    if prime in memoize:
        return memoize[prime]
    if len(prime_str) == 1:
        memoize[prime] = is_prime(prime)
        return memoize[prime]
    if is_truncatable_recursive(int(prime_str[1:])) and is_truncatable_recursive(int(prime_str[:-1])):
        memoize[prime] = True
        return True
    memoize[prime] = False
    return False

n = 100
sum_of_truncatable_primes = sum(num for num in range(10, n) if is_prime(num) and is_truncatable_recursive(num))
print(sum_of_truncatable_primes)

Output:

186

The example employs recursion within the is_truncatable_recursive() function, which checks if the passed prime is already in the memoize cache. If not, the function is called recursively to check both the left and right truncations, storing the results in a memoize dictionary. This recursive method with memoization saves time by preventing repeat calculations.

Bonus One-Liner Method 5: Using Generators

This one-liner uses generator expressions for a compact yet readable solution. It combines the efficiency of a sieve for finding primes with Python’s generator expressions for a succinct one-liner that calculates the sum of all truncatable primes below n.

Here’s an example:

# Re-using sieve_of_eratosthenes from Method 2.
sum_of_truncatable_primes = sum(num for num in range(10, n) if all(sieve[int(str(num)[i:])] and sieve[int(str(num)[:len(str(num))-i])] for i in range(len(str(num)))))
print(sum_of_truncatable_primes)

Output:

186

This approach succinctly combines the sieve of Eratosthenes and concise generator expressions to find and sum all truncatable primes in one line. The outer generator ranges over possible primes and the inner generator expression checks for truncatability using the precomputed sieve.

Summary/Discussion

  • Method 1: Brute Force with Prime Checking. Simple and easy to understand. Inefficient for large n due to many prime checks.
  • Method 2: Sieve of Eratosthenes with Truncation Check. Faster for larger n, as it checks fewer numbers for primes. More complex to implement.
  • Method 3: Early Termination with Prime Set. Further improves efficiency by avoiding unnecessary checks. Requires additional memory for the prime set.
  • Method 4: Recursive Truncation with Memoization. Optimizes repeated calculations by caching. For very large n, recursion could introduce a stack overflow risk.
  • Bonus Method 5: Using Generators. Provides a one-liner solution for the problem. Very elegant, but might be harder for beginners to decipher.