Project Euler Problem 60 Statement

The primes $3$, $7$, $109$, and $673$, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking $7$ and $109$, both $7109$ and $1097$ are prime. The sum of these four primes, $792$, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solution

Project Euler Problem 60 asks for a set of five primes for which any two primes concatenate to produce another prime. The objective is to find such a set with the lowest possible sum. The provided code generalizes this problem to find a set of k primes below a limit n that satisfy this concatenation property.

Code Breakdown

1. Imports and Lambda Functions

import math, Euler
concatenate = lambda a, b: int(f"{a}{b}")

1. The math module is used for mathematical operations, such as calculating square roots and logarithms.
2. The Euler module is used for the prime sieve and the Miller-Rabin prime number check.
3. concatenate() function concatenates two integers a and b by converting them to strings, joining them, and converting the result back to an integer. For example, concatenate(13, 7) returns 137.

2. Generating k-Primes with Concatenation Property (gen_k_prime_set() function)

def gen_k_prime_set(n, k):
    # Precompute compatible primes
    primes = Euler.prime_sieve(n)
    compatible = collections.defaultdict(list)
    for p1, p2 in itertools.combinations(primes, 2):
        if Euler.is_prime_MR(concat(p1, p2)) and Euler.is_prime_MR(concat(p2, p1)):
            compatible[p1].append(p2)
            compatible[p2].append(p1)

    # Recursive search for k-clique
    def search(clique, candidates):
        if len(clique) == k:
            yield clique
            return
        for p in candidates:
            new_candidates = [q for q in compatible[p] if q > p and all(q in compatible[m] for m in clique)]
            yield from search(clique + [p], new_candidates)

	return {frozenset(combo) for p in primes for combo in search([p], compatible[p]) if len(combo) == k}

1. Prime Generation & Precomputing Compatible Primes:
   • Generate n prime numbers.
   • Initializes a dictionary compatible where each prime maps to a list of primes it can be concatenated with to form new primes in both orders.
   • Iterates through each pair of primes (p1, p2), checks if both concatenations (p1p2 and p2p1) are prime using the is_prime_mr() function.
   • If both concatenations are prime, both primes are added to each other's compatibility lists.
2. Recursive Search for k-Clique:
   • Defines an inner function search that performs a recursive depth-first search (DFS) to find cliques (sets) of size k.
   • Clique: A set of primes where every pair is compatible.
   • Procedure:
     1. If the current clique has size k, it yields the clique as a valid set.
     2. Otherwise, it iterates through the candidates, adding compatible primes and recursively searching for larger cliques.
     3. Ensures that any new candidate is compatible with all existing members of the current clique.
3. Collecting Results:
   • Initializes an empty set k_prime_sets to store unique valid sets of primes.
   • Iterates through each prime p and initiates the search for cliques starting with [p].
   • Adds any found cliques of size k to k_prime_sets as immutable frozenset objects to ensure uniqueness.
4. Return Value:
   • A set of all valid k-prime sets

3. Main Execution

N, K = map(int, input().split())
k_primes = gen_k_prime_set(N, K)

# Sort and print the sets based on the sum of their elements
print(*sorted(sum(s) for s in k_primes), sep='\n') 

1. Input: Reads two integers n and k from standard input, separated by space.
   • n: The upper limit for prime numbers to consider.
   • k: The size of the prime sets to find.
2. Generating Prime Sets:
   • Calls gen_k_prime_set(n, k) to find all valid sets.
3. Sorting and Output:
   • Calculates the sum of each prime set.
   • Sorts the sums in ascending order.
   • Prints each sum on a separate line.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 60

HackerRank Project Euler 60: Find the sum of all set of $K-primes$, $(3\le K\le 5)$ for which any two primes $(prime\lt N)$, $(100\le N\le 20000)$ concatenate to produce another prime. Print the sum in sorted order.

Last Word

• The prime_sieve and is_prime_MR functions will be imported instead of hard coded into the source code. This provides flexibility to include different sieves as required to solve a problem.