11–20 of 117 posts
tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…
tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…
Doesn't this have some relation to https://en.wikipedia.org/wiki/Church_encoding
Earlier quoted context omitted.
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...
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 an…
[1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes [2] https://en.wikipedia.org/wiki/Unary_numeral_system
It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.
Very interesting. Thanks for writing this up. This is a bit more Perlish (not that I'm an authority): sub is_prime { (1x$_[0]) !~ /^(?:.?|(.{2,}?)\1+)$/; } But perhaps less clear to a novice reader. You can also leave off the semicolon.
You are probably right, but this function was my first head-to-head encounter with Perl, I researched just a little bit what I needed to know in order to write it.
http://neilk.net/blog/2000/06/01/abigails-regex-to-test-for-...
(check out Abigail's other JAPHs if you like stuff like this)
> How would we go about that? Well, all we have to do is add ? in front of the +. This will lead us to the regex. I was very confused until I realized the author's definition of 'in front' wasn't the same as mine...
> How would we go about that? Well, all we have to do is add ? in front of the +. This will lead us to the regex. I was very confused until I realized the author's definition of 'in front' wasn't the same as mine...
What do you mean? Could you please clarify that? What did your understand by "in front"?
(Which is also how I would normally think of "in front", for what it's worth!)
I wish they'd stop calling these expressions "regular".