Simple mathematical concepts I: Induction.

New equals sign
After reading this and this I realized something is really, really wrong about mathematical concepts out there. Proof by induction is a really, really simple yet powerful proof method.  In this post, I will talk about induction for natural numbers.

Induction is based on two steps, usually called basis and inductive step. I will proof that 1+2+…+n=n(n+1)/2  for all natural numbers using induction.

  1. Basis or base case consists on proving the predicate for an initial value, usually a small one. In the example 1=1*2/2=1.
  2. Inductive step consists on supposing the if the predicate holds for n, then it also holds for n+1. In the example:

1+2+…+n+(n+1)=(n+1)+n(n+1)/2 because we supposed that predicate held for n. We need to prove that this expression is equivalent to (n+1)(n+2)/2. Indeed,

(n+1)+n(n+1)/2=(n+1)(1+n/2)=(n+1)((2+n)/2)=(n+1)(2+n)/2

so the predicate has been proofed for all natural numbers.

Why does induction work?

Think of any natural number, as big as you want. Got it? We know that the predicate holds for 1, and that if the predicate holds for a number it holds for its successor. So it holds for 2, and for 3 and so on until it reach your number.

Other types of induction.

There are several types of inductions. Two of these types are structural induction and complete induction.

Creative Commons License photo credit: hartboy

Problema 2

Enunciado:
Suma todos los números pares de la sucesión de Fibonacci menores que un cuatro millón.

Primera solución:

La primera solución es muy simple. Hay un método que devuelve un array con todos los números de la sucesión de Fibonacci menores que un máximo max tomando como inicio un array de dos elementos arr.

def fib1(max,arr=[1,1])
while(arr.last < max) do arr << (arr.last+arr[arr.size-2]) end arr.pop arr end[/ruby] Después simplemente se eliminan los impares y se suman los que quedan. [ruby] def euler2a(max, ini=[1,1]) fib1(max,ini).delete_if{|x| x%2 == 1}.inject{|memo,obj| memo+obj} end puts euler2a(4e6)[/ruby] Segunda solución:

Esta solución es un poco mejor. Se va a hacer un nuevo método que calcule todos los números de la sucesión de Fibonacci menores que un máximo max pero que sólo almacene aquellos que pasen una condición que se le pasa como bloque:

def fib2(max,a=1,b=1)
arr = []
arr << a if yield(a) while(bTercera solución:

Esta tercera solución es una modificación directa de la segunda. En vez de almacenar los datos, se suman directamente.

def fib3(max,a=1,b=1)
res = 0
res += a if yield(a)
while(bActualización: Hay diferencias entre la página de PyEuler y la del Proyecto Euler. El problema ha sido actualizado para corresponderse con esta última.

Problema 1

Empiezo aquí una serie de artículos de periodicidad variable que lo único que pretende es ser algo similar (de una manera muy amplia) a PyEuler. La lista completa de problemas está en el Proyecto Euler y, como no podía ser de otra manera, empiezo por el primero.

Enunciado:
Halla la suma de todos los números menores que 1000 y múltiplos de 3 o de 5.

Solución 1:

  1. def euler1a(e, numbers)
  2.   (1..e).select{|x| numbers.any?{|y| (x%y == 0)}}.inject{|memo,o| memo+=o}
  3. end
  4.  
  5. puts euler1a(1000,[3,5])

La explicación es simple. Tenemos un rango desde 1 hasta el límite, filtramos los que son múltiplos de algún elemento del array y después se suman.

Solución 2:

  1. def euler1b(e,numbers)
  2.   (1..e).inject(0){|memo,o| (numbers.any?{|x| (o%x)==0}) ? memo+o : memo }
  3. end
  4.  
  5. puts euler1b(1000,[3,5])

Éste es similar al anterior, sólo que se suma según se recorre el rango.

Solución 3:
Para este necesitamos antes un par de funciones. La primera, halla el máximo común divisor de dos números. Para ello, básicamente usa el algoritmo de Euclides.

  1. def mcd(n1,n2)
  2.   if n1 < n2
  3.     mcd(n2,n1)
  4.   elsif (n1%n2) == 0
  5.     n2
  6.   else
  7.     mcd(n2,n1%n2)
  8.   end
  9. end
  10. [/ruby]
  11.  
  12. Por otra parte, está la función que calcula el mínimo común múltiplo. Para ello usa su relación con el <abbr title="Máximo Común Divisor">m.c.d.</abbr>.
  13. [ruby]
  14. def mcm(n1,n2)
  15.   n1*n2/mcd(n1,n2)
  16. end

Con esto, ya podemos pasar a la tercera solución, que es diferente de las otras dos en que sólo sirve si utilizamos dos números como filtro.

  1. def euler1c(limit, n1, n2)
  2.   (n1*((limit/n1)*((limit/n1)+1)/2)+n2*((limit/n2)*((limit/n2)+1)/2)-mcm(n1,n2)*((limit/mcm(n1,n2))*((limit/mcm(n1,n2))+1)/2))
  3. end
  4.  
  5. puts euler1c(1000,3,5)

La explicación es un poco más complicada, pues implica teoría básica de conjuntos y la conocida fórmula de la suma de 1 a n.

Ahora es vuestro turno. ¿Cómo se os ocurre hacerlo?