2008-11-04

Proyecto Euler: Problemas 19 a 21

Sigo avanzando con los ejercicios del proyecto Euler. Les cuento los siguientes 3 ejercicios.
EL ejercicio 19 consiste en contar la cantidad de domingos del siglo 20. Primero pensé en hacer un montón de aritmética modular para resolver esto, pero después se me ocurrió una idea mejor. Así que usé la biblioteca de fechas de ruby, iteré por todos los días de enero del siglo 20 y sumé todos los domingos. Acá abajo pongo el código:


require 'date'

sundays = 0
(1901..2000).each do
|year|
Date.civil(year,1,1).upto(Date.civil(year,1,31)) do
|d|
sundays += 1 if d.wday == 0 # is sunday
end
end

puts "# of sundays in the 20th century: #{sundays}"

El resultado de la corrida (casi instantáneo) es:

$ ruby euler19.rb
# of sundays in the 20th century: 443

El ejercicio 20 consiste en encontrar la suma de los dígitos de 100!. Usando las funciones para obtener cada dígito de un número del ejercicio 16, se hace bastante fácil. Este es el código:

class Integer
def digit(pos)
(self / (10 ** pos)) % 10
end
def digit_count
dc = 0
while self - (10 ** dc) > 0
dc += 1
end
dc += 1 if self % (10 ** dc) == 0
dc
end
end

fact100 = (1..100).inject { |prod,n| prod * n }
puts "Digits: #{fact100}"
puts "Sum: #{(0...(fact100.digit_count)).inject {|s,n| s + fact100.digit(n)}}"

Y el resultado de la ejecución (también instantánea) es:

$ ruby euler20.rb
Digits: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Sum: 648

El ejercicio 21 es el más complicado de los 3. Consiste en sumar todos los números naturales "amigables" menores a 10000. Un par de números (a,b) es amigable si la suma de los divisores de a (excluyendo a) es b y la suma de los divisores de b (excluyendo b) es a. Un número es amigable si pertenece a un par amigable. Lo que se me ocurrió fue usar el MemoFactorizator (factorizador de números que recuerda factorizaciones previas) del ejercicio 12 para calcular las factorizaciones de todos los números menores a 10000. Usando esto, calculé analíticamente las sumas de los divisores propios (hay una fórmula re-linda que sale de la factorización, pero como no puedo escribir LaTeX facilmente acá, mejor mirenla en el código). Y habiendo calculado todas las sumas de los divisores, buscar en orden n todos los números amigables. Acá está el código:

class OddPrimes
def initialize
@current = 1
@primes = []
end
attr_reader :current
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end

def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

class Primes < OddPrimes
def initialize
super
@first = true
end
def next
if @first
@first = false
2
else
super
end
end
def current
odd_super = super
odd_super == 1 ? 2 : odd_super
end
end

class MemoFactorizator
attr_reader :factored
def initialize
@factored = {1 => {} }
end
def factorize(n, pg = Primes.new)
return @factored[n] if @factored.include?( n )
p = pg.current
while n % p != 0
p = p.next
end
factorization = factorize( n / p, pg ).dup
factorization[p] = factorization.include?(p) ? factorization[p] + 1 : 1
@factored[n] = factorization
factorization
end
end

def divisor_sum(n, factorization)
acum = 1
factorization.each_pair do
|p,pow|
acum *= (0..pow).inject(0) { |s,i| s + p ** i }
end
acum - n
end

MAX = 10000

mf = MemoFactorizator.new
(2...MAX).each do
|n|
mf.factorize(n)
end

sums = {}
(2...MAX).each do
|n|
sums[n] = divisor_sum(n, mf.factored[n])
end

amicable = []

(2...MAX).each do
|n|
amicable << n if n == sums[sums[n]] and n != sums[n]
end

puts "Amicable numbers: #{amicable.inspect}"
puts "Sum: #{amicable.inject {|s,n| s+n}}"

La ejecución tardó un poquito (unos 4 segundos) y dio este resultado:

$ time ruby euler21.rb
Amicable numbers: [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
Sum: 31626

real 0m4.681s
user 0m4.560s
sys 0m0.108s

Happy hacking,
Aureliano

1 comentario:

Eugenio dijo...

Hola Aureliano, con esto post me diste ideas sobre que escribir mi abandonado blog;


Saludos!