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