Finding prime numbers using voodoo regular expressions

August 26th, 2009 | Categories: general math, programming, python | Tags:

If you have learned how to program then the odds are that you have written a program that displays a list of prime numbers.  A prime number generator is a programming rite of passage that is almost up there with the ubiquitous ‘Hello World‘ application (for programmers who are going on to do numerical work at least).

There are various ways you might choose to do it but I bet that your first (or even your second or third) thought wouldn’t be ‘I know – I’ll use a regular expression‘. Someone known only as ‘Abigail’ obviously thought that the world desperately needed such a regex since he / she came up with the following incantation

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

Which is a regular expression that I assure you can be used to generate a list of all the prime numbers.  If you are in the mood for a puzzle then sit back, grab a cup of coffee and try to work out HOW it can generate the primes.

If you give up then head over to Python Programming for a full explanation along with Python code that demonstrates that it really does work.

Can anyone come up with regular expressions for other interesting series of numbers?

Update (27th August 2009): Someone pointed me to an alternative explanation here.

  1. August 26th, 2009 at 22:53
    Reply | Quote | #1

    The code looks like pure white noise to me…how can people program in that language :-|

  2. Pseudonym
    August 28th, 2009 at 06:55
    Reply | Quote | #2

    Just so you know, Abigail is definitely a “she”. I’ve met her at a conference.

    But she’s just Abigail. Like Twiggy.

  3. July 14th, 2012 at 09:26
    Reply | Quote | #3

    To be precise, that regex matches composite numbers, so the primes are the set of strings of 1s minus the language generated by the regex.

    And I’m not sure what circumstances would lead to Abigail being a ‘he’ either.

  4. July 14th, 2012 at 14:49
    Reply | Quote | #4

    “And I’m not sure what circumstances would lead to Abigail being a ‘he’ either.”

    If it was a surname.