mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2016-05-25, 08:54   #1
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

142148 Posts
Default 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?
retina is offline   Reply With Quote
Old 2016-05-25, 15:19   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

In unary, sure. It's not possible in decimal (or base k with k > 1).
CRGreathouse is offline   Reply With Quote
Old 2016-05-25, 15:29   #3
axn
 
axn's Avatar
 
Jun 2003

19·271 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
In unary, sure. It's not possible in decimal (or base k with k > 1).
Did you read the article?
axn is offline   Reply With Quote
Old 2016-05-25, 15:42   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by axn View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-05-25, 15:57   #5
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

19×251 Posts
Default

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.
petrw1 is offline   Reply With Quote
Old 2016-05-25, 16:38   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

6D416 Posts
Default

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
Nick is online now   Reply With Quote
Old 2016-05-25, 18:17   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-05-25, 18:19   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2016-05-26, 01:37   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×3×7×233 Posts
Default

Quote:
Originally Posted by danaj View Post
(who is not a "her")
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime numbers test primality - with proof written in invisible ink Godzilla Miscellaneous Math 40 2018-10-17 00:11
Another way to PRP test Mersenne numbers paulunderwood Miscellaneous Math 18 2017-01-26 20:33
Prime numbers Grid, to test an odd integer on 44 Zarck Math 5 2012-03-06 14:43
The fastest primality test for Fermat numbers. Arkadiusz Math 6 2011-04-05 19:39
A primality test for Fermat numbers faster than Pépin's test ? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.