Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Written by on 13 October 2012

Topics: Project Euler

Problem 118 have a very short problem description which in all it’s glory reads

Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.

How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

I see two approaches to this problem of which I have taken one of them. The first solution approach which I have taken is to generate all permutations of the digits 1-9 and then check if you can split them in to ordered sets of primes.

The second approach I have thought of is to generate all primes less than 1.000.000.000 and then start generating sets from these elements.

Outline of the approach

Let me start by giving you the outline of what I have done

for all permutations of the digits 1..9
   for all partitions of the permutation
      for each number n in the partition
          if n is smaller than the previous number or
          if n is not prime reject the sequence

This is the general approach. The reason that we only want sets ordered by size is that otherwise we will generate each set multiple times. Say we have {2,5,47,89,631} we would also generate {5,2,47,89,631} which is not a distinct set and therefore we should not count it.

Coding the parts

We need parts that can produce permutations, partitions, and check if a number is prime. The first part we coded in problem 24 and a prime checker we have used in a whole lot of problems already. So the only thing we really need to worry about is making the partitions.

I guess that when you have a hammer everything looks like a nail. After I started getting in to recursive solutions everything have seemed like a problem that could be solved that way, so once again I have made a solution which is recursive.

The piece of code I have written both makes the partitions and checks if the sequence is valid. After all there is no reason so make all partitions starting with the number 12, since non them will be valid anyway. For the recursive solution I need to know my start index, so I can see where I am at, and I need the previous number in order to check that my results are larger now.

The code looks like

private int CheckPartitions(int startIndex, int prev) {
    int count = 0;
    for (int i = startIndex; i < perm.Length; i++) {
        //form the number x of the digits startIndex -> i
        int number = 0;
        for(int j = startIndex; j <= i; j++){
            number = number * 10 + perm[j];
        }

        //We only count ordered sets,
        //check that the current number
        // is larger than the previous
        if(number < prev) continue;

        //Check that number is prime
        if(!IsPrime(number)) continue;

        // No more digits so return
        if(i == (perm.Length-1)) return count + 1;

        count += CheckPartitions(i + 1, number);
    }

    return count;
}

Wrapping up

This solution rung in 854ms, which is not all that fast. I am pretty sure that the majority of time is spent in the prime checker. I have used a very simple one. If you use one where you have a list of primes to check against, I am sure it will speed things up. However, that was not really the interesting part of this problem

The algorithm gives us the solution

There are 44680 sets

I loved this problem a whole lot, and it took me a while to figure out how to avoid the problem of counting sets multiple times even though it was obvious that you just count the ordered sets…

You can find the complete source code for the problem here.

3 Comments For This Post I'd Love to Hear Yours!

  1. Markus says:

    I was thinking about this problem since quite a while.
    My approach was similar to your’s, but I was missing the idea to search only for ordered primaries. When I read this in your blog I made a few changes in my code and it worked.

    I’m using Perl and the program ran about 40 seconds although I used memoization for either the primaries and the non-primaries.

    Thanks for sharing the idea, it was helpful.

    Markus

  2. Kristian says:

    You are very welcome. I am just glad I could inspire you to a good solution.

    /Kristian

  3. Lurf says:

    I translated the code into mathematica (not exactly the same, but pretty close)
    amt = {1, 2, 3, 4, 5, 6, 7, 8, 9}; x = Permutations[amt]; count = 0;
    solve[index_, prev_] :=
    Block[{i},
    If[index == Length[amt], count++,
    For[i = index, i prev, solve[i + 1, y]]]]];
    Snip[start_, end_] :=
    Block[{i, t}, t = 0;
    For[i = start, i <= end, i++, t = t*10 + cur[[i + 1]]]; t]; For[
    i = 1, i <= Length[x], i++,
    If[Mod[i, 1000] == 0, Print[N[i/Length[x]]]]; cur = x[[i]];
    solve[0, 0]]; count

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.