Blogs Libres

De vez en cuando se me da por hacer saries de posts en el blog. Sagas. Una de las últimas fue la saga sobre resoluciones a problemas del proyecto Euler. Lo que intentaba era resolverlos con alguna característica interesante de Python y luego explicarla. Luego de los primeros, los ejercisios se volvieron más matemáticos y encontraba menos cosas interesantes de Python que comentar, así que dejé de postear mis soluciones. Acabo de encontrar esta entre mis archivos y creo que tiene algo de originalidad como para merecer ser publicada:

¿Cuál es la suma de los dígitos del número 2^(1000)?

>>> 2**1000
107150860718626732094842504906000[algunos números fueron intencionalmente borrados]
>>> a = 2**1000
>>> sum((int(x) for x in list(str(a))))
1366

¿A alguien se le ocurre otra forma?

Enunciado 7

Listando los primeros seis números primos: 2, 3, 5, 7, 11,y 13, podemos ver que el 6° primo es el 13.

¿Cuál es el 10001° primo?

Solución

La solución fue obtenida en el intérprete interactivo de Python 2.5.2:

>>> from math import sqrt
>>> def primo(n):
...     for i in xrange(2,int(sqrt(n))+1):
...         if n % i == 0:
...             return False
...     return True
>>> while i < 10002:
...     if primo(a):
...             i +=1
...     a += 1
...
>>> i
10002
>>> a
104744
>>> a-1
104743

Enunciado 6

La suma de los cuadrados de los primeros diez números naturales es:

El cuadrado de la suma de los primeros diez números naturales es:

Así que la diferencia entre la suma de los cuadrados de los diez primeros números naturales y el cuadrado de la suma es 3025 − 385 = 2640.

Encontrar la diferencia entre la suma de los cuadrados de los primeros cien números naturales y el cuadrado de la suma.

Solución

La solución fue obtenida utilizando el intérprete interactivo de Python 2.5.2:

>>> def a(n):
...     s = sum(xrange(1,n+1))
...     a1 = s ** 2
...     a2 = sum([x**2 for x in xrange(1,n+1)])
...     return a1, a2, a1-a2
...
>>> a(10)
(3025, 385, 2640)
>>> a(100)
(25502500, 338350, 25164150)

Python tips

• Con ** podemos elevar un número a cualquier potencia sin necesidad de importar ningún módulo.
• Para denotar una tupla solo hacen falta las comas (,), no los paréntesis al principio y al final.

Enunciado 5

Solución

La solución fue obtenida ejecutando el siguiente programa Python 2.5.2:

from math import sqrt
from operator import mul, add

def primo(n):
    for i in xrange(2,int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def factorizar(n):
    primos = [x for x in xrange(2,n+1) if primo(x)]
    factores = []
    if n == 1:
        return [1]
    for p in primos:
        if n == p:
                factores.append(p)
                return factores
        if n % p == 0:
                n /= p
                factores.append(p)
                while n % p == 0:
                    n /= p
                    factores.append(p)
    return factores

def mcm(l):
    '''Maximo comun multiplo'''
    ff = [factorizar(i) for i in l]
    singles = list(set(reduce(add,ff)))
    temp = []
    for s in singles:
        temp.extend([s] * max([f.count(s) for f in ff]))
    return reduce(mul,temp,1)

if __name__ == '__main__':
    #print mcm(range(1,11))
    print mcm(range(1,21))

Python tips

• El módulo operator tiene varias funciones útiles equivalentes a operadores como * y + que pueden utilizarse con funciones como reduce, cuyo primer parámetro es una función.
• reduce toma una función f de dos argumentos y una lista l. Aplica f a los dos primeros elementos de la lista y obtiene un resultado, luego aplica la función f al resultado con el tercer elemento de la lista, y así sucesivamente hasta consumir toda la lista y retornar el resultado final. Opcionalmente se le puede pasar un tercer parámetro para que la primer llamada a la función f sea aplicada sobre este y el primer elemento de la lista.

Enunciado 4

Un número palíndromo se lee igual en ambos sentidos. El mayor palíndromo construido a partir del producto de dos números de dos dígitos es 9009 = 91 × 99.

Encontrar el mayor palíndromo que se puede construir como el producto de dos números de tres dígitos.

Solución

La solución fue obtenida en el intérprete interactivo de Python 3.0rc1+. Necesitaba Python 3 para utilizar itertools.combinations:

juanjo@fenix:~$ python3
Python 3.0rc1+ (py3k, Oct 28 2008, 09:23:29)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from itertools import combinations
>>> tri = range(999, 99, -1)
>>> mults = []
>>> for a,b in combinations(tri, 2):
...     s = str(a*b)
...     if s == s[::-1]:
...             mults.append(int(s))
...
>>> max(mults)
906609

Python tips

• combinations genera la combinación con los elementos de la lista argumento tomados de a n, si se especifica el parámetro n.
• En Python 3 print deja de ser una sentencia para convertirse en una función, por lo que siempre debe ser llamado con parámetros.
• unString[::-1] es un idiom usado para invertir una cadena de texto (en el ejemplo, unString). Se lee: los elementos de unString, desde el principio al final, con paso -1.

Enunciado 2

Cada nuevo item en la secuencia de Fibonacci es generado sumando los dos términos previos. Empezando con 1 y 2, los primeros 10 términos serían:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Encontrar la suma de todos los términos pares en la secuencia que no supera los 4 millones.

Solución

La solución fue obtenida en el intérprete interactivo de Python 2.5.2:

>>> MAX = 4000000
>>> def evsum(n):
...     s = 0
...     a,b = 1,2
...     while True:
...         if a >= n:
...             break
...         if a % 2 ==0:
...             print a, " ",
...             s += a
...         a,b = b,a+b
...     return s
...
>>> evsum(MAX)
2   8   34   144   610   2584   10946   46368   196418   832040   3524578
4613732

Python tips

• La asignación múltiple es un idom muy cómodo: a,b = 1,2
• Si agregamos una coma final a la enumeración de objetos a ser impresos con print, se logra el efecto de que no se imprima el salto de línea (\n) final.

Project Euler es un sitio web que reta a los programadores a resolver problemas matemáticos mediante código. Me parece entretenido. Voy a ir resolviendo problemas y posteando mi solución en Python acompañada de comentarios sobre el código que puedan servirles a quienes están empezando a aprender el lenguaje.

Enunciado 1

Si listamos todos los números menores a 10 que son múltiplos de 3 o 5, obtenemos 3, 5, 6 y 9. La suma de esos múltiplos es 23.

Encontrar la suma de todos los múltiplos de 3 o 5 menores a 1000.

Solución

La solución fue obtenida en el intérprete interactivo de Python 2.5.2:

>>> def mults(n=10):
...     r = []
...     for i in range(1, n):
...             if i % 3 == 0:
...                     r.append(i)
...             elif i % 5 == 0:
...                     r.append(i)
...     return r
...
>>> mults()
[3, 5, 6, 9]
>>> sum(mults())
23
>>> sum(mults(n=1000))
233168

Python tips

• En la definición de la función mults se incluye un argumento por defecto n con valor 10. Cuando más adelante se llama a esta función sin parámetros, n toma el valor por defecto.
• La función range, incluida en el lenguaje devuelve una lista de números sobre la que se puede iterar. Muy útil para usar con la estructura for. Más información haciendo help(range) en el intérprete interactivo.