Euler #30

https://projecteuler.net/problem=30 => "Digit fifth powers"

Un poco de culturilla matemática, se trata de "números narcisistas"

def checkSumDigits(number, power):
 _sum = 0
 for digit in str(number):
  _sum += (int(digit))**power
 return _sum == number

final_sum = 0
for a in range(2, 10**6):
 if checkSumDigits(a, 5):
  print a
  final_sum += a
print final_sum

Euler #29

https://projecteuler.net/problem=29 => Distinct Powers

numbers = []
for a in range(2, 101):
 for b in range(2, 101):
  n = a**b
  if not n in numbers:
   numbers.append(n)

numbers.sort() 
print len(numbers)

Euler #28

https://projecteuler.net/problem=28 => Number spiral diagonals

Los problemas en "2D" son siempre entretenidos. El problema es bastante sencillo, pero hay que tener cuidado y llevar un control de en qué dirección vamos y a cuándo "hay que torcer".

import sys

if len(sys.argv) != 2:
 print "Usage: 028.py <SIZE>"
 sys.exit()

table = []
size = int(sys.argv[1])
if size % 2 == 0:
 print "Only odd numbers"
 sys.exit()

for _ in range(0, size):
 row = []
 for _ in range(0, size):
  row.append(0)
 table.append(row)

directions = ((0,1), (1,0),(0,-1),(-1,0))

def get_next_direction(current): 
 i = directions.index(current)
 if i == len(directions) - 1:
  i = 0
 else:
  i += 1
 return directions[i]

max_num = size**2
x = size/2
y = size/2
diagonal_sum = 0
current_direction = (-1,0)
for a in range(1, max_num+1):
 if x == y or x + y == size - 1:
  diagonal_sum += a
 table[x][y] = a
 new_direction = get_next_direction(current_direction)
 x1 = x + new_direction[0]
 y1 = y + new_direction[1]
 if table[x1][y1] == 0:
  x, y = x1, y1
  current_direction = new_direction
 else:
  x, y = x + current_direction[0], y + current_direction[1]

#for row in table:
# print row
print "diagonal_sum", diagonal_sum

Euler #27

https://projecteuler.net/problem=27 => Cuadratic primes

Este problema es muy sencillo, simplemente hay que iterar entre todos los valores posibles para los dos coeficientes (-999 <= a <= 999 y -1000 <= b <= 1000) y comprobar cuántos números primos consecutivos permite calcular el polinomio n² + an + b.

La primera implementación es sencilla y bastante rápida, apenas unos segundos. Pese a que es un problema con un orden de complejidad polinómico por definición (cuadrático para las posibles combinaciones de a y b más otros ciclo para comprobar los números primos), dado que los valores del programa son pequeños, se resuelve en un tiempo razonable.

Pero claro, siempre se quiere optimizar. Así que pensé "si al comprobar si un número es primo o no, puedo tenerlos ya guardados en una lista y así no tengo que calcular lo mismo una y otra vez".

Veamos la implementación, sólo cambia lo siguiente: una lista de números primos inicialmente vacía y una comprobación previa. El resto del código es igual. Sin embargo, al ejecutarlo, nos encontramos con que tarda bastante más tiempo.

¿Qué ha pasado? Fácil, que la supuesta optimización ha resultado ser peor. Con pensar 5 segundos se da uno cuenta por qué: cada vez que queremos saber si un número es primo debemos buscarlo en una lista que cada vez es más grande. Además, debemos asignar memoria y hacer diversas operaciones internas en la lista para redimensionarla al añadir un nuevo elemento. Desconozco la implementación exacta de la búsqueda en listas de Python, pero no puede ser mejor que del orden de O(log n).





Otra forma de crear esta caché de números primos es utilizar un diccionario Python, que requiere menos manejo de memoria, pero la verdad, la mejora, para las dimensiones de este problema, es mínima.

Conclusión: si optimizas, ten cuidado, no sea que lo estropees.

Euler #26

https://projecteuler.net/problem=26 => Reciprocal cycles

Este ha costado un poco más sacarlo, y ha sido gracias al número 1/17 cuando me he dado cuenta que un número sí que se podía repetir en el periodo (asumí que no). Sabiendo eso, la comprobación para ver si estamos empezando un nuevo periodo solo debe tener en cuenta si estamos repitiendo un resto. Veamos una implementación en Python:

from decimal import Decimal, getcontext

getcontext().prec = 40

def Div(D, d):
 return (D/d, D%d)

def GetPeriod(d):
 period = []
 remainders = []
 index = 0
 c, r = Div(1, d)
 if r == 0:
  return []
 if c != 0:
  period.append(c)
 while True:
  D = 10*r
  c, r = Div(D, d)
  if r == 0:
   return []
  period.append(c)
  if r in remainders:  
   return period[period.index(c):index]
  index += 1
  remainders.append(r)

 return period


longestList = []
longestInt = 1
for a in range(1, 1000):
 period = GetPeriod(a)
 if len(period) > len(longestList):
  longestList = period
  longestInt = a

print "Longest period for ", longestInt, " => ", longestList, " (len: ", len(longestList), ")"