This is a fairly old threat but being a number geek myself I would like to add something anyway. First of all I use the term "Circular Primes" instead of "Rotationally Primes" because that seems to be the official name in literature.

There might be an additional "trick" to filter out numbers that cannot be circular prime instead of doing some prime test on each cyclic permutation (worst case).

I recently read paper on absolute primes (sometimes also called permutable primes) by A. Slinko. The rules for absolute primes are even more restrictive, i.e. every possible permutation (instead of only every cyclic permutation) should also result in a prime number. In this paper a survey is given of all known facts referring to absolute primes different from repunits.

Some facts
1. A multidigit absolute prime contains in its decimal representations only the four digits 1, 3, 7, 9. The same applies to cyclic primes and your program already takes this into account (0, 2, 4, 5, 6, 8 are impossible for obvious reasons).

A second theorem is less trivial:
2. An absolute prime does not contain in its decimal representation all of the digits 1, 3, 7, 9 simultaneously. In short the proof takes a certain permutation of the digits constructing a number that has a divisor. Now the proof no longer holds for cyclic primes (e.g. 71993 is a counter example) but it would apply to a subset of numbers (Maybe the proof could be modified to cater for a certain subset of cyclic prime canidates).

Then this could be implemented for cyclic primes as well, i.e. short-circuit if some pattern of digits 1,3,7 and 9 occurs in the number.

Now to get back to your original question: If you really want to find the next one your program needs modifications:

• The standard Perl numbers are nowhere near big enough (I was looking for palindromes in different bases and Math::BigInt seems mandatory).
• A different prime test, when the numbers get bigger you run into problems.

With a little bad luck R19 is the first candidate. The first really interesting candidate is R49081. For this giant number it is still unknown if it is prime or not. Although the real challenge would be to find a circular prime that’s not a repunit.

Sorry for the long post