regex thinks there's a second even prime

Create issue
Issue #367 new
Former user created an issue

(?!(1{2,})\1+$)((?:11)+)$ should match only strings consisting of n '1's, where n is an even prime. But, best I can tell, this returns a partial match for all n greater than 2:

regex.match(r'(?!(1{2,})\1+$)((?:11)+)$', '1' * n, partial=True)

which implies that there is some n that would yield a full match, and thus a second even prime.

We can also see that there exists a number greater than 2 which is an integer power of both 2 and 3:

>>> regex.match(r'(?=(?P<po2>1$|(?P<sd2>1+)(?=\g<sd2>$)(?&po2)$))(?P<po3>1$|(?P<sd3>1+)\g<sd3>(?=\g<sd3>)(?&po3)$)', '11', partial=True)
<regex.Match object; span=(0, 2), match='11', partial=True>

Less sensationally, this also gives a partial match:

regex.match(r'(?!.+).*', '1', partial=True)

So I guess the problem is that partial matching assumes lookaheads are satisfiable. But, as the sillier examples show, it's not enough to consider them independently; you can always add ones to get a prime number or an even number, just not both at the same time.

I don't expect this regex engine to solve every number theory problem that can be expressed in this regexp dialect (though it'd be pretty cool if that turned out to be possible). But the limitations should probably be documented somewhere.

Comments (0)

  1. Log in to comment