• Author / Uploaded
• Priscila Peralta

Citation preview

Problemas propuestos Los números combinatorios, mejor conocidos como coeficientes binomiales, provienen de dos ámbitos. La primera de ellas es la combinatoria: responde a cuántos conjuntos de k elementos distintos podemos hacer si
tenemos n elementos. A este número se le denota por nk . Por otro lado, aparecen en el desarrollo del binomio de Newton ! n X n k n−k n (x + y) = x y k k =0

La definición usual es la siguiente: ! n n! = k k!(n − k)! Con esta definición podemos escribir el siguiente programa from math import factorial def choose(n,k): """ choose(n,k) computes the binomial coefficient INPUT > two positive integer numbers OUTPUT > an integer number """ return factorial(n)/(factorial(k)*factorial(n-k))

Es evidente que este cálculo de los coeficientes binomiales no parece ser muy eficiente. 1. En el código anterior, el programa calcula k!, (n −k!)! y n!. Es fácil ver que se pueden usar los cálculos de uno para calcular los demás: vamos multiplicando los números enteros desde 1 hasta n y en proceso obtenemos tanto k! como (n − k)!. Usar esta estrategia para elaborar un código más eficiente.

2. Existe fórmulas recursivas para los coeficientes binomiales que podrían usarse para calcularlos. En este caso, usamos que ! ! ! n n−1 n−1 = + k k k −1

con k0 = kk = 1 para cualquier k. Usa estas fórmulas para escribir una función recursiva que calcule los coeficientes binomiales. ¿Sabrías reprogramar el código para evitar la recursión usando esta fórmula?
3. Supongamos que k > n − k. La fracción que define a nk permite simplificar a ! n n(n − 1) · · · (k + 1) = (1) k (n − k) · · · 2 · 1 Usa esta simplificación para escribir otro código que calcule el coeficiente binomial. 4. Se puede reescribir (1) como ! Y k n n +1−i . = i k i=1 Inspirados en este producto, pensamos que es posible escribir el siguiente código def binomial(n,k): bin_coeff=1 for i in range(1,k+1): # Running the integer numbers from 1 to k bin_coeff*=(n+1-i)/i return bin_coeff

Pero cuando calculamos binomial(4,3) nos encontramos con que la computadora devuelve 0, ¿qué es lo que ocurre? ¿por qué razón falla el código? ¿Sabrías qué hay que hacer para arreglar el código?

Page 2

5. Es posible conocer el tiempo que tarda la computadora en realizar los cálculos: existe una librería conocida como time donde te calcula la diferencia de tiempo entre dos puntos. Por ejemplo, en el código import time start print end = print

= time.time() "hello" time.time() end - start

muestra cuánto tiempo tarda (en segundos) en imprimir por pantalla la palabra hello. Toma una serie de casos donde los valores de n y k se incrementen y crea una lista con los diferentes tiempos que tarda en calcular el coeficiente binoamial para cada una de las funciones que has creado para tal propósito. ¿Cuál de todos ellos es más eficiente? Recordamos la definición de número primo: un número entero positivo n ≥ 2 es primo (o irreducible) si los únicos divisores positivos que tiene son 1 y n. Decidir si un número entero es primo o no siguen siendo, a día de hoy, objeto de estudio. Si el número es bajo, cualquier computadora de hoy en día podría dar una respuesta con un adecuado algoritmo, pero no así con números con más de 200 dígitos. No es nuestro propósito crear un algoritmo que resuelva el problema, pero sí escribir algún que otro algoritmo. 6. A partir de la definición de número primo, escribe una función que devuelva True o False dependiendo si el número es primo o no. ¿Es necesario comprobar con todos los números k = 2, . . . ,n − 1 si es o no divisor de n? 7. Dado un número entero positivo n, escribe una función que te devuelva una lista con los n primeros números primos. 8. Dado un número entero positivo, escribe un programa que devuelva la factorización de n. Dicha factorización puede almacenarse en una

Page 3

lista que contenga todos los primos que divida a n repetidos según su multiplicidad. La función ϕ de Euler o función indicatriz de Euler se define sobre los números naturales. Dado n, ϕ(n) es el número de enteros menores o iguales a n que son coprimos1 a n. 9. Escribe una función que, dado n entero positivo, calcule ϕ(n) a partir de la definición. Usa para ello el algoritmo del máximo común divisor que aquí presentamos: def gcd(a, b): """Calculate the Greatest Common Divisor of a and b. Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive). """ while b: a, b = b, a %b return a

Asimismo explica porqué razón este algoritmo del máximo común divisor funciona. La función ϕ de Euler tiene una serie de propiedades importantes 1. ϕ(a · b) = ϕ(a)ϕ(b) si a y b son coprimos. 2. Si a y b no son coprimos, entonces la fórmula aparece un factor: d ϕ(a · b) = ϕ(a)ϕ(b) ϕ(d ) donde d es el máximo común divisor de a y b. 3. ϕ(nr ) = nr −1ϕ(n) para cualquier n y r positivos. 10. Deduce a partir de las propiedades anteriores que si la descomposición en factores primos de n es n = p1k1 p2k2 · · · prkr ,

Page 4

entonces ϕ(n) = (p1 − 1)p1k1 −1 (p2 − 1)p2k2 −1 · · · (pr − 1)prkr .

(2)

11. Dado un número entero n, escribe una función que te devuelva ϕ(n) usando la fórmula del problema anterior. 12. También existe otra fórmula: ϕ(n) = n

Y p|n

1−

1 p

!

donde el símbolo p|n debe leerse “p divide a n”. Escribe una función en Python que, dado un entero positivo, calcule ϕ(n) usando esta fórmula. Sea la siguiente sucesión. Dado el primer término de la sucesión x 0 , que debe ser un entero positivo, definimos la sucesión de manera recursiva como sigue  x n−1 /2 si x n−1 es par, xn =   3x n−1 + 1 si x n−1 es impar.  Si x 0 = 12, entonces los siguientes términos de la sucesión serían 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, . . . Si x 0 = 11, tendríamos la sucesión 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . . Observamos que en ambos casos acabamos repitiendo la misma secuencia 4, 2, 1, 4, 2, 1, . . . La conjetura de Collatz afirma que partiendo de cualquier x 0 , la sucesión siempre acabará en algún momento repitiendo esta secuencia. Como toda conjetura, actualmente no está demostrado que eso suceda realmente. 13. Escribe un programa que dado el primer término de la sucesión x 0 y un entero n, la función devuelva los primeros n términos de la sucesión.

Page 5

14. Si la conjetura de Collatz es cierta, dado un x 0 entero positivo existirá un N tal que x N sea el primer elemento de la sucesión que vale 1. Escribe un programa que dado el término inicial de la sucesión x 0 devuelva dicho N . 15. Observamos el siguiente hecho: la sucesión acaba en la secuencia 4, 2, 1, . . . en el momento en el que algún término de la sucesión x N sea 2r para algún r . Por ejemplo, en el caso de x 0 = 11, el término x 10 = 16 = 24 . Escribe una función para que, dado el término inicial, devuelva la potencia más grande de 2 que forma parte de la sucesión. ¿Qué conclusiones sacas? Nuestra notación numérica es posicional: si escribimos 143, lo que realmente estamos escribiendo es 1 · 102 + 4 · 101 + 3 · 100 ; también 4106 = 4·103 +1·102 +0·101 +6·100 . Decimos que la base de nuestra numeración es 10. De este modo, los dígitos van desde 0 hasta 9. Sin embargo, los ordenadores escriben sus números en base 2 y por lo tanto sólo maneja dos dígitos: el 0 y el 1. En este sentido, para un ordenador el número 100101 es 37: 100101 = 1 · 25 + 0 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 32 + 4 + 1 = 37 16. Sea b ≥ 2. Escribe un programa en el que dado un número n, devuelva una lista con los dígitos correspondientes al número escrito en base b.

Page 6

√ n Dados x y n, existe una forma de √ aproximar x. Por ejemplo, se sabe que los babilonios aproximaron 2 mediante el siguiente procedimiento: comenzaban con un número, pongamos por ejemplo 2, y definimos la sucesión de manera recursiva 2x n x n2 − 2 √ donde x 0 = 2; dicha sucesión converge a 2. Si queremos calcular la raíz cuadrada de a, la sucesión sería x n+1 = x n −

x n+1 = x n −

x n2 − a 2x n

con x 0 = a. 17. Escribe una función en Python que calcule la raíz cuadrada de un número x dado. El problema es dar un test de parada, es decir, dar una condición para que el programa termine y dé un resultado. En este caso, puedes tomar que |x n −x n+1 | sea menor que un número pequeño (digamos 10−6 ) y, al ocurrir esto, la computadora te devuelve x n+1 . Es posible generalizar este método para calcular la raíz k-ésima de un número a ∈ R. Sólo hay que modificar la sucesión a x n+1 = x n −

x nk − a kx nk−1

.

donde √ x 0 = a, aunque se puede tomar uno más cercano al valor aproximado n a. 18. Escribe una función análoga al anterior donde calcule la raíz k-ésima de un número a. El test de parada seguiría siendo el mismo.

Page 7