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
.
m
cuando el factorial dem
dividido entren
da un resto diferente de 0. Es exactamente lo mismo quem = 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í.m=1 while True:
?