2

He encontrado en una página web el siguiente código en Python, pero no entiendo muy bien una parte:

from sympy import factorial

def a(n):
    m=1
    while True:
        if factorial(m)%n==0: return m
        else: m+=1

print [a(n) for n in xrange(1, 101)]

El problema que tengo es que la línea: else : m+=1 no sé muy bien que hace.

2
  • 1
    Simplemente incrementa en uno el valor de la variable m cuando el factorial de m dividido entre n da un resto diferente de 0. Es exactamente lo mismo que m = m + 1. No se si tu duda es respecto a que hace en si la línea o es más sobre el algoritmo en sí.
    – FJSevilla
    Commented el 4 mar. 2018 a las 11:30
  • @FJSevilla ¿Y por qué pone al principio m=1 while True:?
    – Carlos
    Commented el 4 mar. 2018 a las 11:49

2 respuestas 2

6

Tu algoritmo lo que hace es generar la secuencia conocida como números de Kempner (generados por la función de Kempner), que no es otra cosa que dado el entero n encontrar el entero positivo más pequeño (m) cuyo factorial (m!) sea divisible por n.

El algoritmo que muestras es el siguiente (vamos a verlo línea a línea):

m = 1
while True:
    if factorial(m) % n == 0:
        return m
    else:
        m += 1
  • m = 1: la idea es buscar el primer entero positivo cuyo factorial es divisible entre 8 (m! % n = 0) debemos siempre empezar por el factorial del primer entero positivo, es decir 1. Por eso lo primero que se hace es asignar a m el valor de 1.

  • while True: como a priori no sabemos cual es el valor de m que cumple la condición m! % n == 0 usamos un ciclo while infinito. Esto se puede hacer de otra forma como veremos después.

  • if factorial(m) % n == 0: esto es el núcleo del algoritmo, comprobamos si el factorial de m (para lo que se usa la función factorial que provee la biblioteca sympy en este caso) es divisible entre n.

  • return m: si el if se cumple (m! es divisible entre n ) retornamos m. Esto ocasiona que la función termine, retorne el valor de m en ese momento y que el ciclo infinito se rompa.

  • else: m += 1: si el if no se cumple (el resto de dividir m! entre n no es 0) se ejecuta el código contenido en el else. Si m no es el entero positivo que buscamos debemos incrementar su valor en 1 (m += 1, ver al final de la respuesta). Esto lo repetiremos hasta que encontremos un m que cumpla m! % n == 0, lo cual causa que la función retorne en el if.

Por ejemplo, para n = 8 la secuencia es la siguiente:

m = 1
m! = 1
1 % 8 = 1
m = m + 1


m = 2
m! = 2
2 % 8 = 1
m = m + 1


m = 3
m! = 6
6 % 8 = 1
m = m + 1


m = 4
m! = 24
24 % 8 = 0
retornamos 4 (primer entero positivo que cumple m! % 8 == 0)


La función puede ser reescrita para evitar dos comparaciones por ciclo moviendo el if a la condición de control del while:

def kempner_num(n):
    m = 1
    while factorial(m) % n:
        m += 1
    return m

No deja de ser pura fuerza bruta, dada la complejidad del cálculo del factorial. Para ciertos valores de n puede ser interesante buscar una aproximación diferente usando las propiedades que tiene la función de Kempner, teniendo en cuenta que:

  • n! es divisible entre n lógicamente. Entonces se cumple que 2 <= s(n) <= n.

  • Si n divide m!, entonces n también divide a todos los factores después de m.


Anexo:

m += 1 es equivalente a m = m + 1 en este caso. Este tipo de sintaxis es conocida como augmented assignment statements y no es más que la combinación, en una sola declaración, de un operador y una instrucción de asignación. En Python existen las siguientes combinaciones:

┏━━━━━━━━━━┳━━━━━━━━━━━━┓
┃Expresión ┃  Similar*  ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i += j   ┃ i = i + j  ┃   
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i -= j   ┃ i = i - j  ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i *= j   ┃ i = i * j  ┃ 
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i @= j   ┃ i = i @ j  ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i /= j   ┃ i = i / j  ┃ 
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i //= j  ┃ i = i // j ┃ 
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i %= j   ┃ i = i % j  ┃ 
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i **= j  ┃ i = i ** j ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i >>= j  ┃ i = i >> j ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i <<= j  ┃ i = i << j ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i &= j   ┃ i = i & j  ┃
┣━━━━━━━━━━╋━━━━━━━━━━━━┫
┃ i |= j   ┃ i = i | j  ┃
┗━━━━━━━━━━┻━━━━━━━━━━━━┛

*No se trata de expresiones equivalentes, i = i + j concatena j a i creando siempre un nuevo objeto resultado de concatenar j e i y reasigna a i la referencia al nuevo objeto. i += j en cambio hace lo siguiente:

  • Intenta hacer la concatenación/suma in-place (similar a i = operator.iadd(i, j)), si el objeto es mutable (list, dict, set, ...) realiza la operación in-place sin crear un nuevo objeto.

  • Si no es mutable (int, float, tuple, str, ...) crea un nuevo objeto, actúa como i = i + j (similar a i = operator.add(i, j)).

Mejor verlo con un par de ejemplos:

  • Objeto inmutable (int, float, tuple, str, etc):

    >>> i = 5
    >>> id(i)
    1972745408
    >>> i = i + 3
    >>> i
    8
    >>> id(i)
    1972745504
    

    La id es única para cada objeto, simplemente es un reflejo de la dirección de memoria de ese objeto. Como podemos ver el nombre i ahora hace referencia a otro objeto. Esto implica que se crea una nueva instancia de int para almacenar i + 3 y luego se le asigna a i. Esto también implica que el antiguo objeto al que hacía referencia i será destruido por el GC cuando haga una pasada y detecte que carece de referencias asociadas. En este caso, al ser int inmutable con += nos pasa lo mismo:

    >>> i = 5
    >>> id(i)
    1972745408
    >>> i += 3
    >>> i
    8
    >>> id(i)
    1972745504
    
  • Objeto mutable (list, set, dict, etc):

    >>> i = [1]
    >>> id(i)
    2379153761544
    >>> i = i + [3]
    >>> i
    [1, 3]
    >>> id(i)
    2379153265672
    

    Como vemos se repite el comportamiento esperado, se hace la operación i + [5] lo que resulta en una nueva instancia de list y este objeto se reasigna a i. En cambio con += pasa algo diferente:

    >>> i = [1]
    >>> id(i)
    2379148377608
    >>> i += [3]
    >>> i
    [1, 3]
    >>> id(i)
    2379148377608
    

    El objeto es exactamente el mismo, en este caso simplemente se concatenado la lista [5] a la lista i in-place, tal como hace list.extend. Una diferencia con este último es que hay una reasignación a la variable i en el caso del operador porque += implica siempre el retorna un objeto (lo cual es congruente con el caso de aplicarlo a objetos inmutables), en este caso se le reasigna la misma referencia al objeto list que tenía antes de la operación, ya que ésta se hace in-place.

La diferencia no es trivial para objetos mutables como cabe esperar:

>>> from timeit import timeit


>>> def foo():
...     a = []
...     b = [1]
...     for _ in range(1000):
...         a = a + b
... 
>>> timeit(foo, number=10000)                 
19.045519875000537


>>> def foo():
...     a = []
...     b = [1]
...     for _ in range(1000):
...         a += b
... 
>>> timeit(foo, number=10000)
0.4562984600015625


>>> def foo():
...     a = []
...     b = [1]
...     for _ in range(1000):
...         a.extend(b)
... 
>>> timeit(foo, number=10000)
0.7102556160007225

Crear un nuevo objeto cada vez, junto a la sobrecarga del recolector de basura al tener que liberar recursos del antiguo, tienen sus consecuencias... La diferencia con list.extend habría que investigarla a fondo, no obstante sospecho que se debe a la sobrecarga de LOAD_METHOD y CALL_METHOD.

0

Si a lo que te refieres es que es exactamente m+=1, eso es lo mismo que decir m = m + 1; es decir, el valor de m es igual al valor de m + 1

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.