4
\$\begingroup\$

The problem is as below:

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.

%%time
import itertools
import time

t1 = time.time()

def prime():

    yield 3
    yield 7

    for i in itertools.count(11, 2):
        e = int(i ** .5) + 1
        for j in range(2, e + 1):
            if i % j == 0:
                break
        else:
            yield i


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    e = int(n ** .5) + 1
    for i in range(2, e + 1):
        if n % i == 0:
            return False
    else:
        return True


def power_up(n):
    # helper function return the next 10 power
    i = 1
    while 1:
        if n < i:
            return i
        i*=10


def conc(x,y):
    # helper function check if xy and yz is prime
    if not is_prime((x*power_up(y))+y):
        return False
    else:
        return is_prime(y*power_up(x)+x)

def conc3(x,y,z): # not use, it did not improve the performance 
    a = conc(x,y)
    if not a:
        return False
    b = conc(x,z)
    if not b:
        return False
    c = conc(y,z)
    if not c:
        return False
    return True




one = []
two = []
three = []
four = []
found = 0

for i in prime():
    if found:
        break
    try:
        if i > sum_:
            break
    except:
        pass
    one += [i]
    for j in one[:-1]:  # on the fly list
        if conc(i,j):
            two += [[i, j]]
            for _, k in two: # check against k only if it is in a two pair
                if _ == j:
                    for x in [i, j]:
                        if not conc(x,k):
                            break
                    else:
                        three += [[i, j, k]]
                        for _, __, l in three:
                            if _ == j and __ == k:

                                for x in [i, j, k]:
                                    if not conc(x,l):
                                        break
                                else:
                                    four += [[i, j, k, l]]
                                    # print(i, j, k, l)
                                    for _, __, ___, m in four:
                                        if _ == j and __ == k and ___ == l:
                                            for x in [i, j, k, l]:
                                                if not conc(x,m):
                                                    break
                                            else:
                                                a = [i, j, k, l, m]
                                                t2 = time.time()
                                                try:
                                                    if (
                                                        sum(a) < sum_
                                                    ):  # assign sum_ with the first value found
                                                        sum_ = sum(a)
                                                except:
                                                    sum_ = sum(a)
                                                print(
                                                    f"the sum now is {sum(a)}, the sum of [{i}, {j}, {k}, {l}, {m}], found in {t2-t1:.2f}sec"
                                                )
                                                if i > sum_:
                                                    # if the first element checked is greater than the found sum, then we are sure we found it,
                                                    # this is the only way we can be sure we found it.
                                                    # it took 1 and a half min to find the first one, and confirm that after 42min.
                                                    # my way is not fast, but what I practised here is to find the number without a guessed boundary

                                                    found = 1
                                                    print(
                                                        f"the final result is {sum_}"
                                                    )

I found the first candidate in 75 sec which I think is to long. I want to see if anyone can give me some suggestion on how to improve the performance.

\$\endgroup\$
3
\$\begingroup\$

The obvious answer is to look again at the primality testing. There's no need to test divisibility by every number up to the square root: it suffices to test divisibility by the primes up to the sqrt. Add a cache and you'll probably beat the minute. For something even faster, look at precomputing all the primes in one sieve. If you want to avoid hard-coding the limit of the sieve, try segmenting it: E.g. sieve up to 1000, and if you need more then sieve 1001-2000, using your knowledge of the primes up to sqrt(2000); etc.

Then the actual search looks rather complicated, and I'm not sure it isn't doing more work than necessary. Have you tried just storing the pairs as a dict from larger to set of smaller and checking triples of those which pair with the current prime under consideration?

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.