@Grimy Awesome! The thing that impresses me the most is that the inequality is precisely equivalent; it's not even off by one, even though there is some wiggle room in which it still makes an overall robust regex. Were you aware that this "power of 2 minus 1" trick was previously used in Is it a Mersenne Prime??

Fixed the anchor bug in RME.

I hadn’t seen Mersenne Prime, but I’ve used power of 2 minus 1 (and power of 2 minus 2, which is the same length) in my log2 regexes

Good work squashing that bug (=

Oh also the variant you used in Mersenne Prime is suboptimal

It's not "wrong", it just doesn't match 0

And hi :)

It should be (x(x+)(?=\3$))+ instead of It (x(x+)(?=\3$))*x

For -1 byte

Hi (=

Yes, I realized that just before you said it

It actually still needs to be 31 bytes, but this fixes the incorrect match of 1 it had.

Alternative 31: ^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx

Or without the final xx, it’s a 29 that incorrectly matches 0 and 1

@Grimy Cool, I was thinking along the same lines, but didn't go as far as coming up with a negative that matches powers of 2 minus 1. Very cool that it came out to be 31.

Here’s a slow 28 that incorrectly matches 0, 1, 2, and 4 ^(?!(x?)(xx\1*(xx)*)(\2x)+$)

Oh actually it has infinitely many false positives (all powers of 2 that are 1 less than a prime)

Not very good

@Grimy If that's true, why doesn't it match 256? That's one less than a prime.

Oh well, I just don’t understand how it works then

And 16

What false positives did you find?

0, 1, 2, 4 I found by testing

"all powers of 2 1 less than a prime" I found by (apparently bad) reasoning

Also this 26 is equivalent ^(?!(x?)((xx)+\1*)(\2x)+$), so if 0, 1, 2, 4 are the only false positives it’s maybe fixable in ≤ 31

Ooh and \1? instead of \1* is still equivalent and considerably faster

@Grimy all sets in order of regex shortness.html - another project in the vein of "busy beavers", but probably more interesting, and using standard ECMA.

@Grimy 26: ^(?!(xx+|(x(x))+)(\1\3)+$)xx (Took me longer than I care to admit to arrive at that)

cc @Deadcode

@H.PWiz Very nice try, but it has an incorrect match of 2

^(?!(xx+|(x(x))+)(\1\3)+$)xxx is still 27 bytes...

Alright, xxx at the end

I miscounted, ^(?!(xx+|(x(x))+)(\1\3)+$)xxx is 29

That's still 2 bytes better...

yes

@H.PWiz The proof of this is not as obvious as that of Grimy's 26/34... have you proven it?

It's effectively an AND between ^(?!(xx+)\1+$)xxx and ^(?!((xx)+)(x\1)+$), but ^(?!((xx)+)(x\1)*$) is what matches powers of 2 minus 1

So, (?!((xx)+)(x\1)+$) works the same as ^(?!((xx)+)(x\1)*$) except that it doesn't reject numbers of the form (xx)+, even numbers. Of which 2 is the only prime

Oooh, awesome. Very nicely done! Are you going to post it as an answer?

yeah, soon

Great job on the 29 (=