// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (19 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 60 Solution

Project Euler 60 Solution

Project Euler 60: Find a set of five primes for which any two primes concatenate to produce another prime


Problem Description

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.

Analysis

Our idea was to use set intersection to quickly find an answer. The problem was that “quick” was not a word to describe this solution. It sounded good, but doesn’t scale well from the parameters described in the problem. Here’s the methodology:
Find pairs of concatenable primes and then use each set to find intersections with other sets. So, for 3 the other primes less than 1,000 that are concatenable are:
3 [7, 11, 17, 31, 37, 59, 67, 73, 109, 137, 191, 229, 271, 331, 359, 373, 449, 467, 499, 541, 557, 607, 613, 617, 673, 701, 719, 733, 739, 823, 929, 947]
So, we need to search each of these sets starting with 7:
7 [19, 61, 97, 109, 127, 229, 283, 433, 487, 523, 541, 547, 673, 691, 757, 823, 829, 853, 883, 937]
The intersection of these sets is:
{109, 229, 541, 673, 823}
Check the above set for 2 primes that can concatenate to make other primes and a 4 prime set is found {3, 7, 109, 673}

Ok, that might work, but I shifted gears and just recursively built a list of primes, two at a time, that could be concatenated. Then took that pair and built a three-prime set. Keep this line of thinking going and after 30 seconds it found the five-prime set.

I randomly selected 10,000 as a prime upper limit thinking it would need to be bigger, but after seeing the results only 8400 would have been sufficient.

Project Euler 60 Solution

Runs < 30 seconds in Python 2.7.
from Euler import prime_sieve, is_prime
import itertools as iter 
primes = prime_sieve(10000)
set_size = 5

def make_chain(chain):
    if len(chain) == set_size:
        return chain 
    for p in primes:
        if p > chain[-1] and all_prime(chain+[p]):
            new_chain = make_chain(chain+[p])
            if new_chain:
                return new_chain
    return False  
        
def all_prime(chain):
    return all(is_prime(str(p[0]) + str(p[1])) for p in iter.permutations(chain, 2))

chain = 0
while not chain:
    chain = make_chain([primes.pop(0)])

print "Project Euler 60 Solution =", sum(map(int, chain)), chain
download arrowUse this link to get the Project Euler 60 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|26033|

Comments

Project Euler 60 Solution last updated

Discussion

7 Responses to “Project Euler 60 Solution”

  1. This code only gives a candidate answer.
    The question asks for the answer with the lowest sum. If the set (3, 7, 109, 311, 18747) would also be valid, it would have a lower sum.

    To remedy for this, you should keep track of the lowest sum found so far, and continue searching until the prime range you used (10000 in your case) is equal to the lowest sum found so far. (You can improve that bound.)

    You were lucky that the answer you found was the correct answer…

    Posted by Pieter | August 8, 2016, 8:33 PM
  2. Hi,
    I ran your python code to Euler 60, and it took almost half an hour. Just like my own code 😉
    Isn’t a runtime under 1 minute a requirement? I was looking for a faster solution than mine…

    Posted by Erwin | May 4, 2016, 3:46 AM
    • Erwin, It runs in under 30 secs in Python 2.7 on an i5 Dell. Perhaps it’s time to upgrade your Atari 400 to something a bit more 21st century.

      Just kidding, actually I don’t know why this solutions runs so slowly for you. Are you using Python 3? Let me know and I will help you resolve the issue.

      Oh, also make sure you are using my library functions as they have been tuned for performance (prime_sieve, is_prime).

      Cheers!

      Posted by Mike Molony | May 16, 2016, 9:09 PM
  3. >>> They are based often on lucky guesses, they’re not scientific and they don’t always give the right answer. They do just because of the lucky guesses I said about.

    Check out the posts by the first 100 solvers. There are flashes of brilliance, but a lot more efforts by hook or crook to get in the door.

    Getting in the door is the primary goal, then the real and directed learning can begin. Sometimes it’s not worth putting lipstick on your pig after get in. In which case there is little to be gained by admitting your solution is a pig.

    Posted by Rex Fury | November 7, 2015, 10:49 AM
    • That’s right Rex, by solving a problem using a computer as a tool is just that – problem solving. Not always elegant in appearance but functional in process.

      Sometimes you have to throw a lot of mud at the wall to make something stick.

      Thanks for your comment – and support.

      Posted by Mike Molony | November 10, 2015, 11:53 PM
  4. Hi D.

    Hey, I’m glad to receive some honest criticism and I thank you for both taking the time to write and to peruse my other solutions.

    I agree that I solve most Euler problems using the “Oracle” method. That means I put some code together and query Euler for a response. If it’s correct I spend some time to improve the solution or implement some aspects of Python that I was learning to help improve performance.

    So, knowing the answer helps a lot. It also helps me reduce brute force search space and that’s not possible if I didn’t know the answer.

    But as for wrong answers? This is news to me. I would love to know more specific problem numbers that produce wrong answers or please tell me how this program fails by using more primes outside the scope of the problem statement.

    Help me improve the experience for others by pointing me to erroneous programs and I will, as time permits, offer deeper explanations.

    In this example, using 50,000 primes, this program calculates 98003 [3, 3119, 9887, 36263, 48731] which is not the answer for this problem but does satisfy the problems requirements sans the lowest sum. So one must reduce the number of primes to check if a lower sum exists and, of course, it does.

    It was very likely, that in 2006, when I first solved this problem, and published a solution in 2009 that I got a wrong answer response from Euler and tried again with a smaller set of primes until I got an accepted answer.

    I know some don’t like this technique, but I focus on getting results and publish these solutions to generate this kind of discussion.

    Would you mind sharing your solution to this problem? I would love to see it and learn from it.

    Thanks again,

    Mike

    Posted by Mike Molony | March 25, 2015, 10:17 PM
  5. Thanks for the idea, the approach is very good, but I find the code quite poor, and this is not the first time.
    I have a general negative comment to your solutions to project Euler.

    They are based often on lucky guesses, they’re not scientific and they don’t always give the right answer. They do just because of the lucky guesses I said about.
    For example, in this problem, if you set up a higher limit for the primes, you obtain a wrong answer.

    For this reason, I would be glad to read more insightful explanations on the way the code is built or the parameters are chosen.

    Posted by D | March 23, 2015, 1:08 AM

Post a comment