Prime pair set finder (Project Euler problem 60)

Question

I made a code that can find the prime sets:

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.

First I made a set of 2 primes that satisfies two conditions.The first condition was the digit sum cannot be 3. The other condition was the concentrating test. After finding these all 2 prime sets, I tried to add the third prime to the set and again I checked these 2 conditions are satisfied. After that, I tried to add the fourth prime and so on.

The problem is, it gives answer in 41 min so what should I do?

import itertools
import time

start = time.perf_counter()
def prime(N):
    if N == 0 or N == 1 or N == 5:
        return False
    for i in range(2, int(N ** 0.5) + 1):
        if N % i == 0:
            return False
    return True


def dig_sum(j, n):  # j is the number, n is the element in the list as tuple
    d = 0
    if j == 0:   
        for k in n:
            d += sum(int(digit) for digit in str(k))
        if d%3 == 0:
            return False
        return True
    else:
        s = sum(int(digit) for digit in str(j))
        for k in n:
            w = s + sum(int(digit) for digit in str(k))
            if w % 3 == 0:
                return False
        return True


def con_test(j, n):  # j is the number, n is the element in the list as tuple
    if j == 0:
        w = int(str(n[0]) + str(n[1]))
        w1 = int(str(n[1]) + str(n[0]))
        if prime(w) == False or prime(w1) == False:
            return False
        return True
    else:
        for i in n:
            w = int(str(j) + str(i))
            w1 = int(str(i) + str(j))
            if prime(w) == False or prime(w1) == False:
                return False
        return True


def st(n):            #to get rid of the repeated elements
    H = [tuple(sorted(i)) for i in n]
    G = set(H)
    return G


Primes = [i for i in range(3,8000) if prime(i) == True]   #Prime range 

Com_two = list(itertools.combinations(Primes,2))

G2 = [i for i in Com_two if dig_sum(0,i) == True and con_test(0,i) == True]

G2r = st(G2)

G3 = [(i,*j) for i in Primes for j in G2r if dig_sum(i,j) == True and con_test(i,j) == True ]

G3r = st(G3)

G4 = [(i,*j) for i in Primes for j in G3r if dig_sum(i,j) == True and con_test(i,j) == True ]

G4r = st(G4)

G5 = [(i,*j) for i in Primes for j in G4r if dig_sum(i,j) == True and con_test(i,j) == True ]

F = [(sum(j),j) for j in G5]

end = time.perf_counter()
Time = end-start
print(Time)
print(F)

Answer 1

This is not so much of a code review question as it is an algorithm review question.

You are calling dig_sum() way too much. You want pairs of primes, which summed together are not a multiple of 3: p1 + p2 != 3n. If p1 % 3 == 1 and p2 % 3 == 2, then these primes must not be paired together. This implies you can partition Primes into two sets: P1 and P2.

P1 = [ p for p in Primes if p % 3 != 2]
P2 = [ p for p in Primes if p % 3 != 1]

Note that 3 is actually part of both sets.

You can then solve the problem using primes from one set, then the other, and choose the lowest sum.

This gives 2 speed ups:

1. Half of the pairs are never considered, being from opposite sets.
2. dig_sum() need never be called, since the pairs will never equal 3.

---

Your prime(N) function can be sped up. You are testing for prime by testing for divisibility by all values from 2 to sqrt(N). You only need to test for divisibility by prime numbers in that range ... and you have a list of Primes. Of course building the list of prime numbers using the prime(N) function, while using that list of prime numbers in that function is a bit of an conundrum... but not impossible. Watch out for special cases.

You could also test if the number is prime by asking if N in Primes:. Making Primes as set() would speed that up, but may also have a disadvantage; consider the pros and cons.

---

Glad to see you are making progress!

Your next improvement will come from further reducing the set of primes you are trying to pair with. for i in P1 is better than for i in Primes because half the primes weren’t even tested. We will further reduce the primes into smaller sets:

If you collect primes from P1 which pair with 3, and then you search the entire P1 space again looking for another prime which pairs with both numbers, you are retesting primes you’ve already rejected.

Instead: collect all primes from P1 which pair with 3. Call that set P1{3}. Then, for each number i in that set, you could look for other numbers j in this smaller set which form a conforming pair.

Better: compute all sets P1{i}. Then you can do set intersections: P1{3} & P1{i}. All numbers j in that intersection form conforming triples (3,i,j).

All numbers k in the intersect P1{3} & P1{i} & P1{j} will form conforming quadruples (3,i,j,k).

And so on.