As promised, here is part 2 of the results of my vigil. This problem describes very special prime sequences. The sequence 1487, 4817, and 8147, has some special properties. First, it is an arithmetic sequence, which means each term of the sequence can be generated by adding some constant to the previous term. In this case the constant is 3330. Next, each term is prime. Lastly, each term is a permutation of the others. There is exactly one other sequence like this of 4-digit numbers, what is it?

My solution to this has the longest runtime of any of the problems I’ve completed yet: 11.528 seconds. Not terrible, but could be a lot better. Here’s the basic approach:

I preloaded all 4 digit primes into a vector, using a text file I generated from some other problem. I have a nested for loop that will check pairs of numbers in the vector to see if they are permutations (which I wrote a isPerm function for). Suppose that they are, then they could possibly be the first two numbers in the sequence I’m looking for. I know they are the first two since my primes list are sorted. Call these two numbers “x” and “y”. Then I can get the next term by adding to y the difference (y-x), since it is supposed to be an arithmetic sequence, that is, z = y+(y-x). I wouldn’t be done yet though, because there’s no guarantee z is the number that completes the sequence I’m looking for. Therefore, it is necessary to check that 1) it is a permutation of x or y and 2) that it is a prime. So for two candidates to the sequence generated by the nested for loop, I check 1) and 2) for the respective “z”.

Here is the code: http://pastebin.com/LRpcjWq0

This turns out to be very slow, even though the number of primes that have 4 digits is only around ~1000 (so that doubly looping through is about ~1000000 loops). I could probably use a better compare function. For isPerm(a,b) works by turn a and b into strings, sorting them, and then checking to see if they are the same. Moreover, it is also probably not necessary to check ALL pairs of primes in my list, but I don’t know what to rule out. I may come back to this later. Regardless, 11.5 seconds still isn’t too long to wait for the answer: 2969, 6299, 9629. Again, the difference of 3330. Coincidence?