Loading...
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.
Use this link to get the Project Euler 60 Solution Python 2.7 source.
You did not find the answer. You guess the boundary is below 10000. you are right. But that is still just a guess. if you set the boundary to 2000000, I don’t know how your code will return a smallest sum.
Posted by MATT | January 15, 2019, 8:18 PMpop(0) has O(n) complexity, use list[n:] will be much faster
Posted by XL | November 15, 2017, 2:50 AMThis 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 PMHi,
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 AMErwin, 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 PMHi 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