/ Published in: Regular Expression

By the legendary abigail. Fails to match if and only if it is matched against a prime number of 1's. That is, '11' fails, but '1111' does not.

I once heard him talk why this works, but I forgot most of it.

Expand |
Embed | Plain Text

^1?$|^(11+?)\1+$

## Comments

Subscribe to commentsYou need to login to post a comment.

This have nothing to see with a "prime number tester"... Fail with 2,3,5,7,9,13,17,19...

And in fact with mostly all number who contain just "1" (1111 is divisible by 11, 11111 is divisible by 41, and 111111 is divisible by 3)

The test works on unary notation, not decimal. So 2 is written as "11", 3 as "111", 17 as "11111111111111111" and so on. The first branch of the regex matches the empty string (representing 0) and "1" (representing 1), marking them as non-primes. The second branch succeeds if and only if the unary number consists of two or more times two or more 1s, which means it is the product of these two numbers (both at least 2), so not a prime. To print a string of primes and see that this works:

See also: http://www.catb.org/jargon/html/O/one-liner-wars.html