Identificando números primos con expresión regular en Perl

Como puede resultar raro que una expresión regular tenga algo que ver con los números primos quiero aclarar algo : este artículo no es una broma. Las  expresiones regulares provienen fundamentalmente de la rama de la teoría de compiladores y son el bloque fundamental de muchos lenguajes de programación. Esto se debe en primer lugar a que son utilizadas por el analizador sintáctico del lenguaje. Además hay librerías para trabajar con expresiones regulares en la gran mayoría de los lenguajes de programación (de alto nivel ;) . Estas expresiones están relacionadas con las  máquinas de estado y algunos  autómatas simples. Otra historia muy diferente son los  números primos, los archi-conocidos guardianes de gran parte de los secretos más celosamente guardados de la  teoría de números. A continuación trato un tema de esos que evidencian las extrañas conexiones entre la informática y las matemáticas y que me dejó sin palabras cuando supe del truco recientemente por primera vez. Antes ya he otras curiosidades similares . Recuerdo ahora por ejemplo el  artículo publicado anteriormente acerca de los  números de Fibonacci. La vida es bella ... y los números y la informática todavía son capaces de sorprendernos. En caso que Usted desee estar al tanto de curiosidades matemáticas semejantes, les invito a  suscribirse mediante RSS.

Los hechos

Para ir directo al grano, la expresión regular es la siguiente :

perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"'

¿Puede darse cuenta de cómo funciona? Más adelante ofrezco una explicación, pero trate de descifrarlo Usted mismo. A continuación les presento lo que ocurre cuando se ejecuta (es preciso teclear el número que se desea comprobar y pulsar la tecla Enter para que el comando facilite la respuesta ;)

$ perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"'
1
2
2 is prime
3
3 is prime
4
5
5 is prime
6
7
7 is prime
8
9
10
11
11 is prime
127
127 is prime
1009
1009 is prime
1234577
1234577 is prime

Con números grandes el comando puede tardar un poco en dar una respuesta. Sea paciente ;)

¿Cómo funciona?

En primer lugar el número es convertido a su representación unitaria mediante (1x$_) . Por ejemplo el número 7 es convertido en 1x7, que es 1111111 (o sea 1 repetido 7 veces ;). En términos generales la idea consiste en aplicar posteriormente la expresión regular que aparece en el miembro derecho a esta cadena. Si se encuentra una coincidencia el número es compuesto sino es primo.

Explicaré a continuación cómo funciona la expresión regular. La misma consta de dos partes ^1?$ y ^(11+?)\1+$. La primera reconoce el número 1 y la cadena vacía. Ambos casos se considera que no son números primos. La segunda determina si dos o más 1s repetidos llegan a conformar una parte del número. Si este es el caso entonces el número es compuesto sino es primo.

Dos ejemplos

Veamos cómo es que funciona todo con los números 5 y 4.

La representación del número 5 es 11111. La expresión (11+?) reconoce los dos primeros dígitos (i.e. 11). La referencia \1 se instancia al mismo valor (i.e. 11) y la expresión regular en sí se expande a ^11(11)+$. La misma no puede aceptar cinco números uno, por tanto falla. Sin embargo, como se utilizó +?, se inicia el mecanismo de backtracking y reconoce los tres primeros dígitos (i.e. 111) . La referencia \1 se instancia al mismo valor (i.e. 111) y la expresión regular en sí se expande a ^111(111)+$. Tampoco tiene éxito ese intento. El proceso se repite para 1111 y 11111, que tampoco aporta una coincidencia. Por tanto la expresión regular en el global no devuelve coincidencia y se concluye que el número es primo.

La representación del número 4 es 1111. La expresión (11+?) reconoce los dos primeros dígitos (i.e. 11). La referencia \1 se instancia al mismo valor (i.e. 11) y la expresión regular en sí se expande a ^11(11)+$. En este caso la representación original sí es aceptada por la expresión regular expandida. Por tanto la expresión regular en el global sí devuelve una coincidencia y se concluye que el número es compuesto.

Conclusiones

Debo dejar claro que no tomo el crédito por haber descubierto este truco. Al parecer fue inventado por  Abigail en 1998. Hay que aclarar que el ejemplo mencionado no es exactamente ni una expresión regular (atendiendo a su definición formal) ni tampoco es un método para verificar si un número es primo. Es simplemente algo raro que se puede hacer con Perl. Le invito a  suscribirse a este blog y así descubrir juntos los secretos de la matemática y la informática.