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.

Después simplemente se eliminan los impares y se suman los que quedan.

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:

Después sólo hace falta pasar el filtro adecuado, y sumar los resultados:

Tercera solución:

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

Y eso es todo.

Actualización: Hay diferencias entre la página de PyEuler y la del Proyecto Euler. El problema ha sido actualizado para corresponderse con esta última.

Tweets del 19-03-2008

• ¿Un objeto imposible? http://tinyurl.com/2nnd7b #

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:

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:

É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.

Por otra parte, está la función que calcula el mínimo común múltiplo. Para ello usa su relación con el m.c.d..

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.

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?

Tweets del 24-02-2008

• Cupones de descuento http://www.retailmenot.com/ #
• Gregory Freeman || Gordon House http://tinyurl.com/33h2zx #
• Diccionario del escéptico http://www.skepdic.com/tilogic.html #
• 100 Kirbies http://www.vgcats.com/comics/ #
• Evolución de Nintendo http://tinyurl.com/2pbzgj #
• El mensaje de Arecibo explicado http://tinyurl.com/3yut35 #
• Los 10 mejores trucos de CSS http://tinyurl.com/3c8lmp #
• Manual de Vim http://www.moolenaar.net/habits.html #
• Cómo leer declaraciones en C http://tinyurl.com/2johzr #
• Manual de ANTLR http://tinyurl.com/3bz4hz #

Tweets del 15-02-2008

• Born to Be Wild http://tinyurl.com/yoc3xj #
• 234 Free Online Cryptogram Puzzles http://tinyurl.com/3dmm7o #

Tweets del 13-02-2008

• Comandos para Mac http://tinyurl.com/2bemuc #
• Transformaciones de Möebius al descubierto http://tinyurl.com/3x22jy #
• Un poco de humor político http://tinyurl.com/yupbcc #
• Cubo de Yoshimoto. http://tinyurl.com/26hgrf #
• Computer Programming Algorithms Directory http://tinyurl.com/a25v3 #
• And She Stares Longingly at What She Has Lost, increíble corto. http://tinyurl.com/2ddxm9 #
• Fotos tomadas en los momentos más oportunos. http://tinyurl.com/ys3s4r #

Matemáticas egipcias.

Hace medio mes empecé mis clases en la Universidad. En Historia de la matemática estamos a punto de llegar a los egipcios, cuya matemática resulta curiosa.

Fracciones unitarias.
Los egipcios ya conocían las fracciones aunque no todas le "gustaban". De hecho, sólo le gustaban las fracciones unitarias (aquellas en las que el numerador es la unidad) y sólo tenía como excepción (o capricho, según se mire): la fracción 2/3. Así, si se encontraban con una distinta, la transformaban en un sumatorio de fracciones unitarias.

Para pasar una fracción del tipo 2/2k a fracción unitaria es muy sencillo: 2/2k = 1/k. El problema viene con fracciones del tipo 2/n con n impar. En el papiro de Ahmes o de Rhind se encuentra una tabla con algunas descomposiciones con fracciones de dicho tipo, exactamente para todos los impares comprendidos entre 3 y 101, ambos inclusive. Sorprende que dichas descomposiciones no son las más "lógicas", es decir, si tenemos 2/k usar 1/k+1/k. De hecho, nadie sabe porqué se eligieron esas descomposiciones y no otras, aunque la mayoría son una de las opciones más simples de descomposoción.

Multiplicación.
Para multiplicar usaban un sistema muy interesante, el de la duplicación. Básicamente, no es muy diferente a la técnica que todos usamos en un principio: la de sumar repetidamente. La única diferencia es que iban multiplicando por dos de forma consecutiva. Así, para multiplicar 4x13:

1 ------------- 4
2 ------------- 8
4 ------------- 16
8 ------------- 32

Así se tiene que 52 = 32 + 16 + 4 = 4·8 + 4·4 + 4·1 = 4·(8 + 4 + 1) = 4 · 13. Que es lo que buscábamos. Para demostrar que es posible con cualquier número, sólo hace falta reseñar que se basa en que cualquier número es expresable en base 2.

Su carencia de fe resulta molesta

"Se traslada a este prisionero desde el bloque uno uno tres ocho" dice Luke Skywalker en La Guerra de las Galaxias: Una nueva esperanza.
Ayer me compré la edición limitada de la primera trilogía. Sí, esa en la que viene como "extra" la versión estrenada en cines. La verdad es que aún no he podido ver las tres, de hecho mientras escribo estoy terminando de ver la primera.

Resulta que ese uno-uno-tres-ocho forma parte del título del primer largometraje de George Lucas: THX-1138. Así pues, me he puesto a indagar sobre ello y he encontrado esta página. En ella se descubre, ¡oh, qué casualidad! que es la primera vez que aparece la palabra Wookie en el cine.

Como todos (aquellos que hayan visto la película) recordarán, poco después caen en un triturador de basura. Lo que no todos recordarán es que el número de dicho triturador es 3263827. Este número me ha resultado curioso y me he puesto a investigar. Lo primero, como siempre, es saber su factorización en números primos. Por el Teorema fundamental de la Aritmética, dicha factorización es única, salvo el orden. Al descomponerlo, resulta curioso que sólo tenga dos factores primos: el 7 y el 466261 (no soy el primero en fijarme en esto). No creo que George Lucas haya estado haciendo números, pero resulta que 1138 también se descompone en dos factores primos: 2 y 569.

Tengo mucho tiempo libre Q.E.D.

One group to rule them all.

Dedicado a un matemático en ciernes, este post tratará de una simple definición del concepto matemático de Grupo, tal vez el primer obstaculillo que se encuentra el estudiante al empezar la carrera.

Un grupo se compone de un conjunto de elementos (por ejemplo, X) y una operación binaria (por ejemplo, *) que cumplen los siguientes requisitos:

1. La operación ha de ser cerrada. Esto quiere decir que cogiendo dos elementos cualquiera de X, se tiene que al aplicar la operación nos da otro elemento de X. En lenguaje matemático se expresa así: ∀ x,y ∈ X | x*y ∈ X.
2. La operación ha de poseer la propiedad asociativa, es decir: ∀ a,b,c ∈ X | a*(b*c) = (a*b)*c.
3. Ha de existir un elemento neutro e que verifique que ∀ x ∈ X | e*x = x*e = x.
4. Ha de existir un elemento inverso x' ∈ X | x*x' = x'*x= e.

Además, si se da la conmutatividad (es decir, para dos elementos cualquiera x,y ∈ X se verifica que x*y = y*x) tenemos que es un grupo abeliano o conmutativo.

Todo este rollo viene para introducir el grupo abeliano de cuatro elementos, o grupo de Klein, que consta de los elementos a,b,c,1. Para terminar de definirlo, sólo hace falta decir que c=ab y que aa=1, bb=1, siendo 1 el elemento neutro del grupo.

Resulta que, visitando la página del difunto Miguel de Guzmán, me encuentro que dicho grupo de Klein se puede emplear para demostrar si una situación final es válida o no en uno de los solitarios de tablero. El artículo completo se encuentra aquí.