5
\$\begingroup\$

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)
\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I tested it but it took just the half amount of time for one pair so its the same as before. Also We need to test for the other pair to see if the our solution is the smallest. So it ll take the same amount of time as before. \$\endgroup\$ Commented Sep 1, 2018 at 11:12
  • \$\begingroup\$ With \$N\$ primes, you have \$N(N-1)\$ pairs. Partitioned in half, you have two sets of \$(N/2)(N/2-1)\$ pairs, which is two sets of 1/4 the total number of pairs, which is results in half the number of pairs, which should result in half of the work. Make sure you are looping over the partitioned set, not the total Primes set for Com_two through G5 inclusive. \$\endgroup\$ Commented Sep 1, 2018 at 13:55
  • \$\begingroup\$ I did cProfile and most of the time was consumed in con_test() but I am not sure what we can do there. I improved my prime function by using an online source (which calculates much faster then my program and reduces to speed up to 8.5min). I tried to import primes from a list but it didnt work very well.I dont know maybe I did smthing wrong about it \$\endgroup\$ Commented Sep 1, 2018 at 15:06
  • \$\begingroup\$ I didnt understand the intersection thing. Or looking primes again part \$\endgroup\$ Commented Sep 2, 2018 at 16:46

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.