7 ms·
A regular expression to check for prime numbers
- _lce0 12y agonice trick! here a JS implementation function isPrime(n) { var re = /^1?$|^(11+?)\1+$/; var s = []; while (n -- > 0) s.push(1); return !re.test(s.join('')); }
- maemilius 12y agoIf I may suggest an improvement: function isPrime(n) { var re = /^1?$|^(11+?)\1+$/, s = (new Array(n+1)).join('1'); return !re.test(s); }
- _lce0 12y agoman that's genius!!
- quadratini 12y agoes6: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/repeat https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- myfonj 12y agoWhy not just function isPrime(n) { return !/^1?$|^(11+?)\1+$/.test(Array(n+1).join('1')) } then? :]
- andrewflnr 12y agoUses back-references, so it doesn't describe a regular language in the strict sense. Still, it's pretty cool to use them to trick a string-processing engine to do integer factoring.
- ubernostrum 12y ago"Regular expression" lost the sense of "strictly only regular languages" around the time that Perl crushed the world. It's probably time to give up on that terminology nit-pick.
- jabagawee 12y agoActually, I think it's still a very important distinction to make. Making this point helps encourage understanding what regular languages, backtracking, et cetera mean, which allows us as engineers use our tools more effectively.
- deleted 12y ago[deleted]
- btilly 12y agoIt actually effectively lost it a bit before. Perl did not invent regular expressions, in fact Larry Wall started with a package by http://en.wikipedia.org/wiki/Henry_Spencer http://en.wikipedia.org/wiki/Henry_Spencer that itself was a reimplementation of an API that appeared in AT&T's V8 Unix that was released in 1985 and was incorporated into standard Unix tools like egrep. Perl standardized a good enough regular expression dialect that everyone else copied it. But the divergence between "regular expression" and "strictly only regular languages" was already a lost cause.
- kazinator 12y agoPOSIX regular expressions (file glob patterns, BRE's and ERE's) have more features than regexes in old CS papers, but they are still regular: they compile to automata with no backtracking.
- schoen 12y agoThe ERE described in egrep(1) has backreferences which can match non-regular languages. Are you thinking of some other notion of ERE?
- btilly 12y agoThis regular expression is due to Abigail of Perl fame. Who is still very active, see http://search.cpan.org/~abigail/ http://search.cpan.org/~abigail/ for more. However while cute, it is very slow. It tries every possible factorization as a pattern match. When it succeeds, on a string of length n that means that n times it tries to match a string of length n against a specific pattern. This is O(n^2). Try it on primes like 35509, 195341, 526049 and 1030793 and you can observe the slowdown. (Some regular expression engines may employ tricks that speed this up over the naive analysis, but none will be super speedy about it.) Usual arithmetic is much more efficient. :-)
- mathattack 12y agoThank you for answering my anticipated question. I was thinking, "There is some beauty here, but this seems very slow relative to other options."
- derekp7 12y agoSome how the beauty of this reminds me of Lambda calculus and Church numerals.
- j2kun 12y agoIt's even worse, because the speed of factoring algorithms is measured against the number of digits of the binary expansion, and this is a unary expansion. So it's really O(2^n^2)
- nhaehnle 12y agoYou really have to put parentheses when building "towers" of exponentials. The bound is (2^n)^2, which simplifies to 2^(2n). This is of course still horrible, but much less so than the 2^(n^2) for which what you wrote may be mistaken.
- quadratini 12y agoIt's right associative, normally :)
- anyfoo 12y agoFor some this will be obvious, but for others it may still be interesting: If this was a "true" regular expression, in the sense that it describes a regular language (http://en.wikipedia.org/wiki/Regular_language http://en.wikipedia.org/wiki/Regular_language), then checking whether the number is prime or not, by checking if the expression matches, would run in linear time. This would be worth a few nobel prizes at least. Unfortunately, it is an "extended" regular expression, i.e. not regular at all in the strictest sense, and (as the article says) requires backtracking.
- btilly 12y agoNot true! First of all there is no Nobel in math/CS. But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting. And a better primality test would not rock the world of cryptography. At the moment http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_... is demonstrably good enough as a prime test that nobody really is hurting for better ones. The thing that you want is a better factoring algorithm. And the General Number Sieve is already subexponential, and so better than any regular expression could be.
- web007 12y agoM-R is a probabilistic primality test, with a deterministic variant for some ranges and a general-deterministic variant dependent on GRH. Lots of people want a better test, so we have Lucas-Lehmer and APRT-CL and AKS. Better primality testing would be interesting to the crypto community, but it could rock the math world - like "Primes is in P" introducing AKS as the first deterministic polynomial time primality test. As you said, though, better factoring would be game-changing for both cryptography AND mathematics.
- raiph 12y agoI've heard that, on modern cpus, with the first 100 or so primes cached, for all but the most performance sensitive applications, MR can be run with sufficient accuracy that there's a greater likelihood that a stray neutron will flip a bit in the cpu at the time of computing MR than that MR will produce an incorrect result. Or something like that. Is it true than MR can be tuned to be as useful as a non-probabilistic test?
- Amorymeltzer 12y agoWe all learned this way back with the Regex Game: http://regex.alf.nu/6 http://regex.alf.nu/6
- logicallee 12y agoless sexy when you write /^(11+?)\1+$/ is a prime test on whether a unary string > 2 is composite then people have a real chance of figuring it out. (go ahead and try, if you haven't read the article.) As it stands that 1 x shift is super confusing. who would have thought 1 would become a literal! we wouldn't even write it that way in english.
- nsajko 12y agoIt uses a string of '1' as a unary numeral representation of a number and then checks it for divisibility with 2,3,4... using brute force.
- geertj 12y agoThis one has been going around for a while. I'd be curious to see a base-2 or base-10 variant of it.
- elzr 12y agoThis is indeed beautiful. But the author limits itself to a low-level unpacking of the regex and running a few tests cases, all the while remaining mystified as to why this works. A high-level description helps makes obvious what's happening: To check the primality of a number N with string matching, repeat a string (say, "1") N times and declare N prime: UNLESS the repetitions match the string 0 or 1 times OR the repetitions can be EVENLY matched into groups of MORE than one string.
- city41 12y agoI wouldn't say he remained mystified. His exploration of the 9 case basically explained how it worked, just the author chose to leave it a bit implied for the reader to figure out. I would agree for a blog post it's usually better to hammer the point home though.
- okey 12y agoEvidently beauty is in the eye of the beholder.
- charlesacknin 12y agoNice (abuse of regexp) ! AFAICT the way the string is going to be parsed is equivalent to this: def isprime(n): if n == 0 or n == 1: return False i = 2 while i <= n: if (n - i) % i == 0: return False i += 1 return True A parser implementation may optimize and do "while (n - i) >= 1" instead, which cuts in half the number of iterations.
- jdmichal 12y agoA better implementation will only check to sqrt(n), as there can be no prime factor greater than that.
- punee 12y agoYes, there can.
- tom-lord 12y agoThe point is that if there is a prime factor greater than sqrt(n), then your will have already found its co-factor by then.
- jdmichal 12y agoCorrect. I misspoke. I should have said, A better implementation will only check to sqrt(n), as there can be no prime factor greater than that without there also being a prime factor lower than that.
- TheLoneWolfling 12y agoIs there a way to write a (non-regular, of course) regular expression that checks for prime numbers in a non-unary base?
- Someone 12y agoIf there were, there would be finitely many repunit primes (via the pumping lemma and the notion that there are arbitrary large non-prime repunits). Edit: that's not quite correct. The above would imply some simple structure in repunit primes. If you add the known asymptotical behaviour of the 'number of primes < N)' function, I think it would imply it. Also, in binary, it would either imply there are finitely many Mersenne primes, or that there is a N such that all Mersenne numbers larger than N are prime (edit: Mersenne numbers are repunits in binary)
- avinash 12y agoThanks for sharing. This is a post I wrote way back in 2007 and, even though, as many have pointed out, the algorithm is very inefficient, it is still a good illustration of how powerful regular expressions are. When I am explaining the basics of regular expressions to people, I always refer them to this post to make them realize that regular expressions are not only glorified search terms. In general, they are amazed :-)
- fxn 12y agoI explored this technique applied to a few other problems just for fun, integer square root, coprimes, continued fractions, modulo, etc. https://github.com/fxn/math-with-regexps/blob/master/one-liners.sh https://github.com/fxn/math-with-regexps/blob/master/one-lin...
- tom-lord 12y agoI'm currently working on a ruby gem to generate examples of given regular expression. For example: /this|is|awesome/.examples # => ["this", "is", "awesome"] So, I tried it out on this "prime number validator" regex: /1?|(11+?)\1+/.examples #=> ["", "1", "1111", "111111", "11111111"] /1?|(11+?)\1+/.examples(max_repeater_variance: 50, max_group_results: 100).uniq.sort.map(&:length).first(10) #=> [0, 1, 4, 6, 8, 9, 10, 12, 14, 15] require 'prime' Array(1..100) - /1?|(11+?)\1+/.examples(max_repeater_variance: 50, max_group_results: 3000).uniq.sort.map(&:length) == Prime.first(25) #=> true Horribly inefficient, but pretty cool! Here's my gem if case anyone's interested: https://github.com/tom-lord/regexp-examples https://github.com/tom-lord/regexp-examples
- arielpts 12y agoThank you very much for your great gem :) Very usefull!
- tom-lord 12y agoThanks :) It's still "under development", while I add a few missing features, but as you can see from the README these are only for fairly obscure parts of the regex language! - E.g. POSIX groups, named properties, character set intersection, ...
- xyzzyz 12y agoIt has been posted before [2], so I'll repost my comment from back then [3]: It's cool, but it's regexp, not regular expression -- regular expressions cannot test for primeness. The proof is a simple application of pumping lemma[1]: we want to show that language { a^p: p prime } is not regular. Suppose it is. By pumping lemma we have numbers N, n >= 1, such that for every k >= 0, we have a^(N+nk) in our language. But that means that for every k, N+nk is prime, and it fails for k = N, since N+nN = N(1+n) is not a prime, since both N and 1+n are greater than 1. [1] - http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu... [2] - https://news.ycombinator.com/item?id=3391547 https://news.ycombinator.com/item?id=3391547 [3] - https://news.ycombinator.com/item?id=3391572 https://news.ycombinator.com/item?id=3391572
- ekimekim 12y agoAn aspect of the syntax is confusing me here. I would have assumed that the expression 'x+?' would be parsed as '((x)+)?', ie. 'x*'. However, it seems the parser special-cases this as (x)(+?) instead, and interprets that as a non-greedy operator. Isn't this horribly inconsistent?
- bantic 12y agoThe thing that made this click for me was realizing the "1" in the regex was not special. The regex is just looping through integers (starting with 2) and checking if the target number is divisible by any of them. It can use any digit if the target string uses the same digit. Ruby example using 5 instead of 1: def is_prime(n); str = "5"*n; str !~ /^5?$|^(55+?)\1+$/; end The regex essentially says, for integer n, "does 2 ones fit evenly into n ones", then "does 3 ones fit into n ones", etc., which is the same as "does 2 fit into n", "does 3 fit into n", etc.