Fracciones continuas (3) - Ecuaciones diofánticas

Una aplicación importante de las fracciones continuas y sus reducidas es la de resolver ecuaciones diofánticas lineales del tipo Ax+By=C, en las que C es múltiplo del MCD de A y B (que son las que poseen solución). Quiere esto decir que A,B y C se pueden simplificar hasta conseguir que MCD(A,B)=1. En lo que sigue supondremos que esto se cumple.

Efectivamente, en una entrada anterior se vio que la diferencia entre dos reducidas consecutivas equivalía a una fracción de numerador la unidad y de denominador el producto de sus denominadores. Esta propiedad también se cumple entre la última reducida y la fracción dada.

Vemos cómo se aprovecha esta propiedad para resolver la ecuación.

Sea, por ejemplo, la ecuación 244X+108Y=112.

Simplificamos: 61X+27Y=28, con MCD(61,27)=1

Buscamos las reducidas de la fracción 61/27 y elegimos la última 9/4



Y se cumplirá, según la propiedad citada, que 61*4-27*9=1, luego 4 y -9 serán las soluciones de 61X+27Y=1. Bastará multiplicar por el término independiente 28 para obtener una solución: X=4*28 = 112 e Y=-9*28 = -252

Las demás soluciones se obtienen mediante las paramétricas.

X=112-27t
Y=-252+61t

Si se desean soluciones positivas deberemos ajustar el parámetro t

Fracciones continuas (2) - Reducidas

En una entrada anterior desarrollamos la fracción 1280/345 en forma de fracción continua, formada por los cocientes [3,1,2,2,4,2], como puedes comprobar fácilmente con las hojas de cálculo fraccont.ods y fraccont.xls.


Debajo de los cocientes aparecen una serie de fracciones, llamadas reducidas o convergentes, que se van aproximando a 1280/245: 3/1, 4/1, 11/3, 26/7, 115/31 y 256/69, que resulta ser la fracción desarrollada, 1280/345, pero simplificada.

Puedes ver esta aproximación en los desarrollos decimales que figuran debajo en la hoja de cálculo.

Estas reducidas se forman calculando fracciones parciales de izquierda a derecha:

3=3; 3+1/1=4; 3+1/(1+1/2)=11/3…

La hoja de cálculo fraccont.ods (en su hoja dedicada a números fraccionarios) logra estas reducidas mediante un algoritmo clásico llamado de “los cumulantes”. Consiste en construir dos sucesiones recurrentes del tipo

P_n = p_n-1*a_n+p_n-2

siendo a_n la sucesión de cocientes de la fracción continua, precedidos en la primera fila por 0 y 1 y en la segunda por 1 y 0. Como ejemplo, si se aplican los cumulantes a la sucesión 1,1,1,1,1…. Resulta la sucesión de Fibonacci 1,1,2,3,5,8…

Puedes seguir estos cumulantes en las filas que contienen los numeradores y denominadores de las reducidas.


Las reducidas permiten la aproximación a una fracción con numerador y denominador grandes mediante otras que están construidas con números más pequeños. Esta utilidad la usaban los torneros cuando carecían de ruedas de determinado número de dientes y debían sustituirlas, con un pequeño error, por otras ruedas más pequeñas.

Por ejemplo, si deseamos que unos engranajes produzcan 2009 revoluciones en un eje y 2000 en otro, sus números de dientes deben seguir la proporción 2009/2000, pero se pueden sustituir por 223/222 con un error inferior a 0,000005.

La reducidas son alternativamente mayores y menores que la fracción dada, y se acercan a ella, pues la diferencia entre dos reducidas es siempre igual a la unidad dividida entre el producto de sus denominadores.

Fracciones continuas (1) – Definición

Durante este otoño iremos comentando una técnica muy poderosa pero algo olvidada, que es la de las fracciones continuas. Con ellas puedes simplificar fracciones, aproximar números irracionales, resolver ecuaciones diofánticas, etc. Para no aburrir a nuestros visitantes, se irán publicando de forma alternada con otros temas de más actualidad.

Llamamos fracción continua a la expresada de esta forma:

donde a es entero y b, c…son enteros positivos llamados cocientes. Toda fracción ordinaria se puede expresar de esta forma, y todo número irracional admite aproximaciones mediante desarrollos de este tipo. Las fracciones continuas se usan cuando se desea manejar una representación de los números reales independiente del sistema de numeración.

Por comodidad tipográfica las fracciones continuas se representan por el conjunto de sus cocientes: [a,b,c,d]

No es este blog el espacio más adecuado para estudiar todo su desarrollo teórico, que puedes encontrar en los siguientes enlaces:
http://es.wikipedia.org/wiki/Fracción_continua
http://sisbib.unmsm.edu.pe/BibVirtual/monografias/Basic/alanya_ps/contenido.htm

Nuestro interés aquí será la implementación de los algoritmos necesarios en hoja de cálculo para desarrollar un número en fracciones continuas y las aplicaciones que derivan de ello.

Si consultas la teoría descubrirás que los cocientes a, b, c,… son los que aparecen en el algoritmo de Euclides para el cálculo del m.c.d. de dos números. Así, por ejemplo, para encontrar el m.c.d. de 345 y 1280, en el algoritmo se obtienen los siguientes cocientes: 3,1,2,2,4,2



En el desarrollo mediante fracciones continuas de 1280/345 vuelven a aparecer los mismos cocientes 3,1,2,2,….¡porque se trata del mismo algoritmo orientado de forma diferente! En la siguiente imagen, capturada de la hoja de cálculo fraccont.ods (En Excel fraccont.xls),


puedes comprobar la evidente igualdad de la serie de cocientes. Comprueba que, efectivamente, es válido este desarrollo:

Expresado de otra forma: 1280/345 = [3,1,2,2,4,2]

Por tanto, el encontrar el MCD de dos números m y n se puede simultanear con el desarrollo en fracciones continuas.

(Continuará)

Números automórficos

Los números de la primera columna de la siguiente tabla son automórficos.Si los estudias adivinarás pronto qué propiedad tienen para recibir este nombre.

¿Cómo podríamos encontrarlos con una hoja de cálculo? Para construir la tabla que se incluye se han usado macros, pero se puede prescindir de ellas. Puedes crear una tabla de números consecutivos y después aplicarles una condición.
Esta tabla es complementaria de la anterior. ¿Qué relación tiene con ella?

Primos reversibles (Primo-Omirp)

Es muy popular la definición de los pares de números primo-omirp, o primos reversibles, que son aquellos en los que uno se forma invirtiendo las cifras del otro y que ambos son primos, como los pares 199 y 991, 7589 y 9857. Se suelen excluir los capicúas.

No vamos a insistir en el concepto, que incluso se recoge en la Wikipedia, sino en la posibilidad de encontrarlos con Hoja de Cálculo.

Para ello necesitamos las dos funciones que definimos en una entrada anterior: INVERTIR_CIFRAS y ESCAPICUA. Además, deberemos contar con la función ESPRIMO, uno de cuyos posibles códigos incluimos al final de la entrada.

Si te animas, encontrarás (excluyendo capicúas) 4 parejas de dos cifras (13 – 31, 17 – 71, 37 – 73, 79 – 97), 14 parejas de tres cifras, desde 107-701 hasta 991-199, y 102 de cuatro cifras. Puedes ordenar bien los cálculos usando las mencionadas funciones (de ESCAPICUA puedes prescindir)



Código de la función ESPRIMO 'Devuelve un 1 si es primo y un 0 si es compuesto

Public function esprimo(a) as integer
dim ai as long
dim n as long
dim es ai=abs(int(a)
if ai=1 then es=0
if ai=2 then es=1
if ai>2 then
n=2:es=1
while n<=sqr(ai) and es=1
if ai MOD n=0 then es=0
n=n+1
wend
endif
esprimo=es
end function

Proporciones relativas

“Recientes estudios estadísticos han puesto de manifiesto que de cada veinte maltratadores condenados, sólo uno sobrepasaba los dos metros de estatura. Aconsejen, por tanto, a sus amigas y conocidas que se emparejen con hombres altos, que vivirán más tranquilas”

¿Qué te parece esta conclusión? Descabellada, ¿no? Pues en nuestra vida diaria a veces razonamos de forma similar. El otro día oí en la televisión este comentario: “De cada 50.000 accidentes de tráfico, sólo en 400 estuvieron involucrados autocares, lo que demuestra que son más seguros que los turismos” Estoy totalmente de acuerdo con la última afirmación, pero no con el modo de obtenerla. Deberían darnos el dato del número de turismos y autocares que circulan por término medio en nuestras carreteras. De esa forma, dividiríamos el número de accidentados entre el número total de cada clase, y así obtendríamos la proporción de accidentes de cada uno, lo que nos permitiría evaluar qué porcentaje es mayor. En este caso, seguro que sería el de turismos, pero con los datos de la noticia eso no se deduce.

Otra afirmación sobre tráfico: “Las carreteras secundarias son más peligrosas que las autovías, porque en aquellas se producen muchos más accidentes de tráfico”. ¿No habría que dividir entre el número de kilómetros existentes en España de cada clase de vía? Y si alguien nos dijera que los camiones son más peligrosos de noche, porque a esas horas están más involucrados en accidentes que los turismos, ¿no necesitaríamos otros datos? ¿no hay tramos en los que de noche prácticamente sólo circulan camiones?

Cuando no vivía en Madrid, los amigos y familiares que viajaban a la capital nos traían de regalo un décimo de lotería, porque “en Madrid toca más”. El mismo fenómeno se da cuando se compra la lotería en Sort, fiados en una mayor probabilidad de obtener premio, ya que en esa localidad se dan muchos. A pocas personas se les ocurre comparar los premios con los números vendidos en esas ciudades.

El error básico que cometemos en estos razonamientos es el de usar cantidades absolutas, y no proporciones relativas o porcentajes. Para comparar la incidencia de un fenómeno cualquiera deberíamos plantearnos una tabla de doble entrada, rellenarla con las cantidades absolutas y después proceder a convertirlas en porcentajes.

Veamos esta, que podemos imaginar perteneciente a una empresa

	Hombres	Mujeres
Fuman	34	13
No fuman	46	14
Proporción	42,5%	48,2%

Si entráramos en la sala de fumar veríamos muchos más hombres que mujeres, y sin embargo sólo fuma el 42,5% de hombres frente a un 48,2% de mujeres.

Ya sabes, ten cuidado: si preguntas en tu parque a la gente que pasea si es diabética o no, no deduzcas de los resultados que a los diabéticos no les gusta tomar el sol.

Cuadrado del simétrico o simétrico del cuadrado

Claudi Alsina, en su libro “Vitaminas matemáticas”, señala como una propiedad del número 12 la siguiente: 12² = 144 y 21² = 441, es decir, que el cuadrado de su número simétrico en cifras coincide con el simétrico de su cuadrado.

Esta propiedad la poseen otras parejas de números, en concreto hay, si la hoja de cálculo no falla, las siguientes:

Dos parejas de dos cifras: 12 y 21, 13 y 31

Cinco parejas de cuatro cifras, desde 102 con 201 hasta 311 y 113

Dieciocho de cinco cifras, desde 1002-2001 hasta 3111-1113

Cuarenta y una parejas de cinco cifras…

Una cuestión sencilla: ¿Qué cifras no pueden figurar entre las componentes de esos números? ¿Cuál es la causa?

Otra algo más compleja: De las cifras que pueden figurar, ¿qué combinaciones de ellas habría que desechar?

Y más difícil, porque hay que contar bastante: ¿Por qué aparecen estos números de parejas?: 2 de dos cifras, 5 de tres cifras, 18 de cuatro y 41 de cinco…

Si deseas emprender una búsqueda ordenada con hoja de cálculo, puedes usar las funciones invertir_cifras y escapicua que se explicaron en entradas anteriores.