Prime pair set finder (Project Euler problem 60)
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:


Half of the pairs are never considered, being from opposite sets. 
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} &amp; P1{i}.  All numbers j in that intersection form conforming triples (3,i,j).

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

And so on.