Calculando el Conjunto de Wirt (entrada antigua)

(esta entrada estaba originalmente en Electrónica a Martillazos, como tener un hosting gratuito se volvió una pesadilla, he decidido copiar las viejas entradas aquí y mandar la web original al olvido. Como son entradas muy viejas, es posible que algunos links estén más muertos que Altavista, Enjoy!). 

Una implementación mejor está aquí.

En la página de PuntoPeek encontré el siguiente problema propuesto: "Calcular los n primeros números del conjunto de Wirth".

El conjunto de Wirth se define de la siguiente manera:

"El conjunto de Wirth es un subconjunto de los enteros positivos que cumple con la siguiente regla: el 1 pertenece al conjunto y si un numero k pertenece al conjunto entonces los números 2*k+1 y 3*k+1 pertenecen al conjunto."

Ya antes había intentado resolver el problema con un algoritmo que, a pesar de dar la respuesta correcta, resultaba muy ineficiente.

La solución de PuntoPeek es mucho mejor. No calcula números extra.

Por mi parte, no hubiera seguido insistiendo con el problema del Conjunto de Wirth si no hubiera tenido la sensación que la solución es mucho, pero mucho más simple.

Para empezar me basé en la solución propuesta de PuntoPeek. Luego de analizarla a simple vista, noté que todo se reduce a:

1. En un array de tamaño fijo n ingreso el 1 como primer elemento,

2. Recorro todos los números naturales y le pregunto a cada uno: ¿eres el resultado de tomar un número k del array y realizar las operaciones: 3k+1 ó 2k+1? si es así, te añado al array.

3. Me detengo hasta completar todos los elementos del array.

Lo curioso es que el postulado del conjunto de Wirth hace pensar en una operación "y" (and lógica): "Si un número k es elemento del conjunto, también lo son los números 3k+1 y 2k+1", cuando en realidad es un or lógico: cada número k del conjunto genera 3k + 1 y 2k + 1. Entonces, para que otro número i sea del conjunto debe cumplir cualquiera de estas dos condiciones: i = 3k + 1 ó i = 2k + 1. O mejor dicho: (i-1)/3 ó (i-1)/2 debe darnos un número k que ya está en nuestro array..

Con el método de PuntoPeek se buscan los primeros números n preguntando si cumplen cualquiera de las dos condiciones. La variable k es conocida, pues ya está almacenada en el array.

En Python, el algoritmo es:

Uso datos de tipo float (coma flotante) para descartar los números que den resultados decimales (la variable i es en realidad un entero con representación flotante). Así evito falsos positivos o falsos rechazados por los errores que se introducen al redondear la división entre enteros.

El resultado es:

Lo interesante de este algoritmo es que sirve para generar cualquier serie de números que cumplan una condición. Basta cambiar los primeros elementos del array y la condición, pues lo que en realidad hace es extraer del conjunto de los números naturales todos aquellos números que cumplen una condición.

La serie Fibonacci se genera de la siguiente forma (como no implica divisiones, no necesito números de coma flotante):

Para las potencias de 2:

Para los factoriales (números que son el factorial de otro):

El script completo es:

def Wirt(n):
    result = [1.0]

    i=1.0
    while len(result)<=n:
        i+=1.0
        if (i not in result and ((i-1)/2 in result or (i-1)/3 in result)):
            result.append(i)

    return [int(x) for x in result]

def Fib(n):
    result = [0, 1]

    i=0
    while len(result)<=n:       
        i+=1
        if i== result[-1] + result[-2]:
            result.append(i)       

    return result

def Pot2(n):
    result = []

    i=0
    p=0
    while len(result)<=n:       
        i+=1
        if i== 2**p:
            result.append(i)
            p+=1

    return result

def Fact(n):

    def fact(p):
        if p==1:
            return p
        else:
            return p*fact(p-1)

    result = []

    i=0
    p=1
    while len(result)<=n:       
        i+=1
        if i== fact(p):
            result.append(i)
            p+=1

    return result

print Wirt(50)
print Fib(10)
print Pot2(10)
print Fact(5)
 

Lo malo de este algoritmo: para el caso del factorial y las potencias de dos es lentísimo. Tarda horas (literalmente) en calcular potencias de 2 mayores a 2^20, y lo mismo sucede para factoriales mayores al factorial de 10. Ir preguntando a cada número si cumple una condición es muy ineficiente para series de números cuyos valores crecen de forma geométrica o exponencial.

Pero ha sido una buena práctica de aprendizaje :)