Proyecto Euler - Problemas 5 a 10

Sigo a full con el Proyecto Euler. Y hoy hice 6 problemas. Les cuento como los solucioné:
El problema 5 es bastante fácil. Esencialmente se trata de encontrar el mínimo común múltiplo de los números 1..20. Lo más molesto es que ni el divisor común mayor ni el mínimo común múltiplo están en mi versión de ruby (ruby 1.8.6 patchlevel 111, ubuntu hardy), así que lo implementé:

class Integer
 def gcd(other)
   values = [self > 0 ? self : -self, other > 0 ? other : -other]
   a = values.min
   b = values.max
   while (a != 0)
     a, b = b % a, a
   end
   b
 end
 def lcm(other)
   self * other / self.gcd(other)
 end
end

puts (2..20).inject(1) {|ac, n| ac.lcm(n)}

Sólo por curiosidad, el número me dio 232792560.
El problema 6 es calcular la diferencia entre la suma de los cuadrados y el cuadrado de la suma de una secuencia 1..n (con n=100). Tampoco fue muy difícil.

class Integer
 def sum_square
   (1..self).inject(0) { |acum,n| acum + n * n }
 end
 def square_sum
   ((self * (self+1)) / 2) ** 2
 end
end

puts 100.square_sum - 100.sum_square

También por curiosidad, el resultado es 25164150.
El problema 7 es encontrar el primo número 10001. Para eso usé la criba que definí en el post anterior e iteré hasta el primo nro 10001.Acá va el código:

class OddPrimes
  def initialize
    @current = 1
    @primes = []
  end
  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

op = OddPrimes.new
p = 2
(2..10001).each {
  p = op.next
}

puts p

El primo que dio es el número 104743.
El problema 8 es medio rebuscado. Lo que me resultó más difícil es entender el enunciado. Te dan un número gigante y tenés que buscar cuáles son los 5 dígitos consecutivos que multiplicados dan el número más grande. Como en el problema 4 había implementado como obtener un dígito arbitrario y la cantidad de dígitos de un número, usé eso y resolví el asunto.

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

n = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

pos = -1
prod = -1
(0..995).each do
 |p|
 candidate = n.digit(p) * n.digit(p+1) * n.digit(p+2) * n.digit(p+3) * n.digit(p+4)
 if candidate > prod
   pos = p
   prod = candidate
 end
end
puts "Digits: #{n.digit(pos)}, #{n.digit(pos+1)}, #{n.digit(pos+2)}, #{n.digit(pos+3)}, #{n.digit(pos+4)}"
puts "Position: #{pos}"
puts "Product: #{prod}"

El resultado que dio es:

Digits: 9, 7, 8, 9, 9
Position: 631
Product: 40824

El problema 9 consiste en buscar número a,b,c tal que son enteros a+b+c=1000 y a^2+b^2=c^2 (teorema de pitágoras para triangulos rectos). Para hacer eso, busqué una tripleta (a,b,c) tal que la suma divida a 1000 y después multipliqué cada número. La verdad es que este problema me costó un ratito. Acá va el código.

#Find a triplet that fits the pitagoras formula and its components divide 1000
def primogenial_triplet
 (3..100).each do
   |c|
   (2...c).each do
     |b|
     (1...b).each do
       |a|
       return [a,b,c] if a ** 2 + b ** 2 == c ** 2 and 1000 % (a+b+c) == 0
     end
   end
 end
end

tr = primogenial_triplet
factor = 1000 / (tr[0] + tr[1] + tr[2])
puts tr.map {|x| x * factor}

Los a,b y c que encontré son: 200, 375 y 425 respectivamente.
El problema 10 es el más interesante hasta ahora. El mismo consiste en sumar los números primos menores a 2000000. Primero usé el generador de primos que tenía, y lo implementé, pero tardó más de un minuto. El código es:

class OddPrimes
  def initialize
    @current = 1
    @primes = []
  end
  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

op = OddPrimes.new
sum = 2
while ( (p = op.next) < 2000000 )
  sum += p
end

puts sum

Pero me quedé enojado porque tardaba mucho, así que googlié un toque y encontré este post que mostraba otra forma de generar números primos. Y lo implementé. La idea es ir marcando todos los múltiplos (menores a un número dado) de los números primos que voy encontrando para encontrar los primos sin hacer divisiones. Y anduvo más rápido. Igualmente, hay que notar que gasta bastante más memoria que la versión anterior. Así que tiene un trade-off distinto entre memoria y tiempo de procesamiento. El código está acá:

MAX = 2000000

class OddPrimes
  def initialize(max)
    @max = max
    @prime_matrix = [false,true] * ((max / 2) + 1)
    @prime_matrix[1] = false
    @current = 1
  end
  def next
    while not prime?(@current += 2)
      throw :max_reached if @current >= @max
    end
    mark
    @current
  end

  def mark
    i = @current
    step = @current * 2
    while (i<@max)
      @prime_matrix[i] = false
      i += step
    end
  end
  
  def prime?(n)
    @prime_matrix[n]
  end
end

op = OddPrimes.new(MAX)
sum = 2
catch :max_reached do
  while ( (p = op.next) < MAX )
    sum += p
  end
end

puts sum

Esta solución corrió en 6 segundos:

$ time ruby euler10.rb
142913828922

real    0m6.179s
user    0m5.780s
sys     0m0.356s

Voy a tratar de seguir resolviendo los problemas del proyecto Euler, así que sigan sintonizados.
Happy hacking,
Aureliano.