Match strings whose length is isolated prime [closed]

Question

Isolated prime definition from Wikipedia:

An isolated prime is a prime number p such that neither p − 2 nor p + 2 is prime. In other words, p is not part of a twin prime pair. For example, 23 is an isolated prime since 21 and 25 are both composite.

Consider strings which consists of character x repeated n times, where n ≥ 0. You shall write a regex which matches strings whose length is an isolated prime, and rejects strings whose length is not an isolated prime.

Same rule as my previous question Match strings whose length is a fourth power:

• Any (ir)regular expression syntax is allowed, except for arbitrary code execution (to Perl users).
• Your solution should logically¹ work correctly for large number. This means that an answer that lists out all the lengths within certain range is disqualified.
• Please also include a short explanation about your approach to the problem (something like this).

_{¹ Some engine implements * with an upper limit. This question assumes that * doesn't have an upper limit (and the only limit is the length of the input string).}

This question on SO might be useful as a starting point. How to determine if a number is a prime with regex?

Do you know?

If you can solve this problem, with trivial modification, you can check whether a number is part of a twin prime, since isolated prime has opposite definition of a twin prime.

Answer 1

Perl, 54

/^(?!(..+)\1+$)(?=..(?:|(..+)\2+)$)(?=(..(.*))\4\3*$)/

I think this is not possible without the Perl look-ahead expression... Firstly, there is no positive regex to match the prime number. You can only match a non-prime by simulating multiplication: (..+)\1+. To negate it, I use negative look-ahead: /^(?!(..+)\1+$)/ matches prime numbers (neglecting the 0, 1 case).

The beauty of the look-ahead is that it is zero-width, i.e. eats no characters. This means you can actually AND those conditions! My regex is composed of 3 look-aheads, corresponding to AND-ing 3 conditions:

• (?!(..+)\1+$) - N (length of the string) is the prime number
• (?=..(?:|(..+)\2+)$) - N-2 is a non-prime - this is a trival modification of the basic non-prime expression - (..+)\1+) - just add two characters. The (?:|...) is included to also match an empty string (case N=2 should match too).
• (?=(..(.*))\4\3*$) - N+2 is a non-prime - again, trivial modification of the basic non-prime expression - cut two characters out of one repetition.

Test:

$ perl -E'($"x$_)=~/^(?!(..+)\1+$)(?=..(?:|(..+)\2+)$)(?=(..(.*))\4\3*$)/&&say for(2..200)'
2
23
37
47
53
67
79
83
89
97
113
127
131
157
163
167
173