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.

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

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

/Kristian

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

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];

}

You don’t need the inner j loop.

int number = 0;

for (int i = startIndex; i < perm.Length; i++) {

number = number * 10 + perm[i];

// do your checking and everything here

}

I used basically the same method as Kristian, but with one modification that cut the runtime in half using the following facts:

In any set of primes covering all 9 digits 1-9, there can be no sets with a single number consisting of all 9 digits. All such numbers are divisible by 9, since the sum(1-9) is divisible by 9. So all prime sets consist of at least 2 members.

Using the rule that a unique set starts with the smallest prime in the set, it is obvious that the largest leading prime in a set consists of no more than 4 digits.

I created a sieve with max value of 20000 (higher primes covered by a Miller-Rabin test), then looped through all primes < 9999 with unique digits. For each of these primes, I set the first element of a prime set as this number, then ran through all permutations of the remaining digits to find the remaining members of a prime set. For instance, for a prime value of 2, run through all permutations of digits starting with 13456789. For a prime value of 349, run through all permutations of digits starting with 125678, etc.

This got me the correct answer of 44680 with a run time of 343 ms.

Just as a point of interest, you can easily write down all the ways of partitioning a set of 9 elements. If you order the subset sizes smallest to largest, there are only 30 ways. Then you can rule out the partition that contains all 9 elements because any permutation of all 9 digits is guaranteed divisible by 3. And you can also rule out 5 partitions that contain more than 4 single digit numbers because there are only 4 single digit primes.