Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Is there a way to write a (non-regular, of course) regular expression that checks for prime numbers in a non-unary base?


If 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)




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: