3 ms·
Is there a way to write a (non-regular, of course) regular expression that checks for prime numbers in a non-unary base?
by TheLoneWolfling 12y ago
Is 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)