Prime pair sets

I started playing around with Project Euler way back in November 2011, not least as an opportunity to hone my still nascent Python skills. And I’m still learning.

Problem 60 states:

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.

This took a bit of thinking about but the approach I eventually came up with was to create a set of concetanatable primes for each prime (up to an arbitarily chosen value of 10000). Then all I would need to do is search each set for intersecting elements until I found five intersecting sets. Since the primes are generated in order, from lowest to highest, the first set of five intersecting sets will give me the answer.

Then for the implementation…

I already have a function that returns a list of primes, so that was easy, and using a dictionary keyed by prime was a no-brainer, but looking for set intersections was a bit of a struggle. Until I discovered that Python will do it for me. Using the set class it becomes remarkably easy to build a dictionary of sets and then work through them, checking intersections, until I find five sets that intersect.

My actual code is neither nice nor fast, and it isn’t going to scale at all – but I am quite pleased to have gained a handle on yet another iterable type.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s