mersenneforum.org Regex can test for prime numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-25, 08:54 #1 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 142148 Posts Regex can test for prime numbers In PERL: Code: perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' {your number here} http://neilk.net/blog/2000/06/01/abi...prime-numbers/ But you already knew that, right?
 2016-05-25, 15:19 #2 CRGreathouse     Aug 2006 3×1,993 Posts In unary, sure. It's not possible in decimal (or base k with k > 1).
2016-05-25, 15:29   #3
axn

Jun 2003

19·271 Posts

Quote:
 Originally Posted by CRGreathouse In unary, sure. It's not possible in decimal (or base k with k > 1).

2016-05-25, 15:42   #4
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by axn Did you read the article?
Not at the time I posted -- it was down. But looking at it now it looks like the standard unary trick.

 2016-05-25, 15:57 #5 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 19×251 Posts Cool uber geeky!! alas doesn't go very high perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' 11113 Prime perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' 111113 Complex regular subexpression recursion limit (32766) exceeded at -e line 1.
 2016-05-25, 16:38 #6 Nick     Dec 2012 The Netherlands 6D416 Posts It's an impressively short test, but it uses an extension to regular expressions which violates the theoretical definition, so it does not follow that there is a finite automaton for determining prime numbers. Last fiddled with by Nick on 2016-05-25 at 16:48 Reason: typo
2016-05-25, 18:17   #7
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by Nick It's an impressively short test, but it uses an extension to regular expressions which violates the theoretical definition, so it does not follow that there is a finite automaton for determining prime numbers.
Right -- matching them, even in unary, requires extended regex in the sense of Câmpeanu-Salomaa-Yu. I don't think even that is enough in binary or decimal.

 2016-05-25, 18:19 #8 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 Posts It primarily comes up in code golfing, where using the fewest characters is the goal, and performance is irrelevant. It's horrendously slow. Abigail (who is not a "her") deserves credit for finding a really inventive use of regexes (as Nick points out, they're no longer regular). It's like a dancing bear juggling kittens. You're in awe of the sight. Some people fail to notice that it's a terrible dancer, the kittens are terrified, and at 32k the bear kills the kittens and falls down. Note that you can install and use re::engine::RE2 to make it go past the 32k limit. It's still gawdawful slow. Last fiddled with by danaj on 2016-05-25 at 18:29 Reason: exponential in input size is clear from the "trial divide by 1..n-1" behavior, don't want to conflate.
2016-05-26, 01:37   #9
LaurV
Romulan Interpreter

Jun 2011
Thailand

2×3×7×233 Posts

Quote:
 Originally Posted by danaj (who is not a "her")

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 40 2018-10-17 00:11 paulunderwood Miscellaneous Math 18 2017-01-26 20:33 Zarck Math 5 2012-03-06 14:43 Arkadiusz Math 6 2011-04-05 19:39 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 18:40.

Fri Oct 22 18:40:05 UTC 2021 up 91 days, 13:09, 0 users, load averages: 1.92, 1.66, 1.49