lunes, 19 de abril de 2010

Proporción entre cubo y cuadrado

Una entrada reciente del blog Números  y otra más antigua de este mismo blog me han sugerido una cuestión:

Dados dos números primos distintos p y q, ¿es posible siempre encontrar un cubo perfecto y un cuadrado perfecto que cumplan
con k y m números naturales siendo p y q primos distintos?

La respuesta es afirmativa, y además, con infinitas soluciones ¿por qué?

Por ejemplo, para p=2 y q=5 las primeras soluciones son k1=10, m1=20, k2=40, m2=400, k3=90, m3=1350…

lunes, 12 de abril de 2010

Factorización de Fermat a paso de tortuga

(Esta entrada constituye la participación de este blog en el Tercer Carnaval de Matemáticas)

La factorización de Fermat siempre se ha presentado como una técnica para representar un número impar como producto de dos de sus factores sin usar la lista de números primos. No es el único algoritmo de factorización con esa propiedad. Si extraemos progresivamente el factor más pequeño (mayor que 1) de N aseguraremos que hemos encontrado un número primo sin tener que memorizar la lista de primos (busca la herramienta factores en la dirección http:/www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm y estudia su funcionamiento).

En efecto, la factorización de Fermat no se basa en los factores primos, sino en representar un número impar N como una diferencia de dos cuadrados y después expresar la misma como el producto de una suma por una diferencia, con lo que se logra la factorización:

N=y2- x2=(x+y)(y-x)

En el caso impar esta operación siempre es posible, porque N=(N+1)2/4-(N-1)2/4, que da lugar a la factorización N=N.1

Desde el punto de vista algorítmico, la búsqueda de los valores de x e y adecuados presenta también otra originalidad, y es que se puede organizar de forma bastante eficiente sólo con sumas y comparaciones. En realidad, todos los algoritmos se pueden organizar así, y en caso último mediante la máquina de Turing, pero tampoco hay que llegar tan lejos. En la búsqueda de la factorización de Fermat se logran resultados bastante aceptables. Es una tortuga, pero algo veloz.

La creación del algoritmo se basa en estos hechos que te pedimos intentes justificar:

(1) El valor de y, y por tanto el de x, están acotados, y su cota no está excesivamente alejada de n ¿Cuál es y cómo se demuestra?

(2) Para demostrar que un número es cuadrado perfecto, no es necesario dividir ni extraer la raíz cuadrada ¿Cómo se hace?

(3) En realidad, la factorización de Fermat consiste en darle al número impar la figura de escuadra simétrica (gnomon) de varias formas posibles. Observando la imagen puedes resolver las dos primeras cuestiones.



(4) Podemos encontrar la raíz cuadrada entera de un número haciendo crecer de forma simultánea dos sucesiones, una linealmente y otra de forma cuadrática. Esto parece obvio, pero ¿cómo se organiza?

Podemos representar el algoritmo como una carrera, liebre y tortuga, entre a=x2 y b=y2, en la que la tortuga sale con ventaja porque se suma al número N, ya que ha de ser  y2=x2+N. Todo esto suena a metáfora, pero funciona.

Daremos a continuación un desarrollo en el que se ocultarán algunos detalles para hacer pensar un poco a quien lo siga.

Obtención de un primer valor de a=y2

Tomamos tres variables, y, a, i
Las iniciamos a y=1; a=1; i=1
Mientras a no sobrepase a N hacemos crecer estas variables así: y=y+1; i=i+2; a=a+i
con lo que lograremos el primer cuadrado que es mayor o igual que N
Sólo hemos usado sumas y una comparación. Razona por qué se da este resultado.

Obtención de valores adecuados de a=y2 y de b=x2

Una vez obtenido y2 iniciamos el crecimiento de la misma forma para x2
x=1; b=1; j=1
Mientras N+b no sobrepase a y2, hacemos crecer las variables:
x=x+1; j=j+2; b=b+j
para formar el cuadrado x2

Si ocurre que N+b=a hemos conseguido una factorización, pues N=y2-x2

Obtenemos todas las coincidencias

Ya sólo queda hacer crecer  a b de la misma forma y comprobar si se da la igualdad N+b=a en más ocasiones, y así hasta la cota.

No hemos querido usar el lenguaje algorítmico, y se han ocultado algunos detalles, como qué hacer si N es un cuadrado perfecto. Lo importante de lo explicado es que sólo hemos sumado y comparado. No se ha recurrido a multiplicar, dividir o extraer la raíz cuadrada.

Puedes estudiar más a fondo el algoritmo en las hojas de cálculo factorfermat.ods y factorfermat.xls, contenidas en el archivo http:/www.hojamat.es/blog/factorfermat.zip

Si recorres el código de la macro usada, sólo verás operaciones de sumar. El proceso no es un prodigio de velocidad, pero esto es un divertimiento. La idea de hoy no era correr, sino demostrar una posibilidad. Tampoco corrió Fermat y hay que ver lo que logró.