Regular Expression That Checks If A Number Is Prime

Re:Regular Expression That Checks If A Number Is Prime by jlarocco on Thursday September 08, 2016 @08:13PM (#12458676)

That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though.

There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-S...

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by Chinjut on Thursday September 08, 2016 @08:21PM (#12458721)

Sure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular).

But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in any nontrivial base.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by jayshua on Thursday September 08, 2016 @09:28PM (#12459044)

What do you mean by "non trivial base?"

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by Chinjut on Thursday September 08, 2016 @10:18PM (#12459251)

Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by jerf on Friday September 09, 2016 @09:05AM (#12461752)

It's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.

[ Parent | on HN ]