¿Podríamos conseguir que cualquier número nos transmitiera dos números de forma simultánea sin ninguna ambigüedad, como ocurre con los semiprimos? La respuesta es afirmativa.
Observa estas factorizaciones: 24=4*6, 144=12*12, 600=24*25, 72=8*9,…
Los factores están elegidos de tal forma que dado un número (no necesariamente semiprimo) puedas adivinar qué factores te desean transmitir. Por ejemplo, ¿qué factores te transmite 120? Si has adivinado el método, sabrás que se trata de 120=10*12.
La idea es descomponer un número natural cualquiera en dos factores de forma que su diferencia sea mínima, escribiendo por convenio el menor delante del mayor.
¿Es única esta representación? Intenta demostrarlo o razonarlo.
Podemos llamar categoría rectangular C de un número N (la denotaremos por C(N) ) a la mínima diferencia (en valor absoluto) existente entre a y b al recorrer todas las factorizaciones de dos factores, es decir la diferencia entre el par de factores que se han propuesto aquí. Por ejemplo C(600)=25-24=1, C(120)=12-10=2, C(23)=23-1=22
Los números con C(N)=0 serán los cuadrados, y los de C(N)=1 los oblongos. En los números primos se cumplirá que C(p)=p-1
En la dirección
http://www.hojamat.es/sindecimales/divisibilidad/propuestas/rutas/htm/ulam.htm
puedes consultar una curiosa relación de la función C(N) con la espiral de Ulam.
sábado, 19 de diciembre de 2009
miércoles, 16 de diciembre de 2009
Primos, semiprimos y casi primos (2)
Las definiciones de semiprimo y k-casi primo nos permiten crear clases de equivalencia en los números naturales. Al conjunto de todos los k-casi primos se le representa por Pk. Así, P1 estará formado por los números primos, P2 por los semiprimos, P3 por los 3-casi primos, etc.
Conseguir esta clasificación con hoja de cálculo requiere partir de un algoritmo de factorización de números naturales (sólo consideraremos un nivel elemental) e incluirle un contador de factores primos.
La siguiente tabla se ha conseguido con un algoritmo de este tipo:
P1 P2 P3 P4 P5 P6
2 4 8 16 32 64
3 6 12 24 48 96
5 9 18 36 72 144
7 10 20 40 80 160
11 14 27 54 108 216
13 15 28 56 112 224
17 21 30 60 120 240
19 22 42 81 162 324
23 25 44 84 168 336
29 26 45 88 176 352
La primera columna está formada por primos, la segunda por semiprimos, la tercera por 3-casi primos, y así hasta k=6. Una curiosidad divertida es la de seguir la secuencia natural de números 1, 2, 3, 4, … en esta tabla e interpretar sus oscilaciones.
El núcleo del algoritmo es el de averiguar k, es decir, el número de factores primos de un número.
Copiamos a continuación las líneas fundamentales de este algoritmo:
Se supone que n es el número, f el factor primo que se va probando y m el contador que recogerá el número de factores:
f=1 (se comienza con factor 1)
while n>1 (esta condición controla el final del algoritmo)
f=f+1 (se prueba otro número)
while n/f=int(n/f) (se pregunta si ha encontrado un divisor)
m=m+1 (si es divisor, aumenta el contador)
n=n/f (se divide el número entre el divisor encontrado para acelerar la búsqueda)
wend wend
msgbox(m) (se comunica el resultado)
Es evidente que este algoritmo se ralentiza en cuanto n es un número de bastantes cifras, y de ahí la utilidad de los semiprimos en ciertas codificaciones.
Conseguir esta clasificación con hoja de cálculo requiere partir de un algoritmo de factorización de números naturales (sólo consideraremos un nivel elemental) e incluirle un contador de factores primos.
La siguiente tabla se ha conseguido con un algoritmo de este tipo:
P1 P2 P3 P4 P5 P6
2 4 8 16 32 64
3 6 12 24 48 96
5 9 18 36 72 144
7 10 20 40 80 160
11 14 27 54 108 216
13 15 28 56 112 224
17 21 30 60 120 240
19 22 42 81 162 324
23 25 44 84 168 336
29 26 45 88 176 352
La primera columna está formada por primos, la segunda por semiprimos, la tercera por 3-casi primos, y así hasta k=6. Una curiosidad divertida es la de seguir la secuencia natural de números 1, 2, 3, 4, … en esta tabla e interpretar sus oscilaciones.
El núcleo del algoritmo es el de averiguar k, es decir, el número de factores primos de un número.
Copiamos a continuación las líneas fundamentales de este algoritmo:
Se supone que n es el número, f el factor primo que se va probando y m el contador que recogerá el número de factores:
f=1 (se comienza con factor 1)
while n>1 (esta condición controla el final del algoritmo)
f=f+1 (se prueba otro número)
while n/f=int(n/f) (se pregunta si ha encontrado un divisor)
m=m+1 (si es divisor, aumenta el contador)
n=n/f (se divide el número entre el divisor encontrado para acelerar la búsqueda)
wend wend
msgbox(m) (se comunica el resultado)
Es evidente que este algoritmo se ralentiza en cuanto n es un número de bastantes cifras, y de ahí la utilidad de los semiprimos en ciertas codificaciones.
domingo, 13 de diciembre de 2009
Primos, semiprimos y casi primos (1)
Un número natural N es k-casi primo para otro natural k dado si la descomposición factorial de N contiene exactamente k números primos iguales o diferentes. Así, 27 es 3-casi primo, porque 27 =3*3*3, 225 es 4-casi primo, dado que 225 = 3*3*5*5.
Para k=1 tendremos los números primos, con un solo factor.
Para k=2 serán 2-casi primos los semiprimos, que son producto de dos factores primos, como 15=3*5, o 77=7*11.
Averiguar si un número es semiprimo equivale a descubrir sus dos factores, pero si estos son muy grandes, la operación puede exigir varios años de cómputo en un ordenador potente. Por ello se usan en el método RSA de encriptación de datos mediante claves públicas y privadas.
Profundizando algo más en el tema, con unos sencillos convenios se puede considerar que un número semiprimo nos da dos informaciones distintas de manera única. Por ejemplo, si convenimos en que cada número que recibamos por algún medio se considere como un producto de filas y columnas, con el número de filas no superior al de columnas, al recibir un número semiprimo podremos construir un rectángulo (una matriz) a partir de él de forma única.
Por ejemplo, si recibimos el número 91, lo podemos interpretar de forma única como el rectángulo 7*13. Es evidente que esto no ocurre con los demás números, como por ejemplo 63, que puede representar 7*9 o 3*21.
Esta propiedad permite transmitir ciertas informaciones de forma lineal simple. Si se recibe una serie de 35 dígitos como 27366524358291002738296634283912836, con el convenio anterior nos han enviado esta matriz:
2736652
4358291
0027382
9663428
3912836
Para k=1 tendremos los números primos, con un solo factor.
Para k=2 serán 2-casi primos los semiprimos, que son producto de dos factores primos, como 15=3*5, o 77=7*11.
Averiguar si un número es semiprimo equivale a descubrir sus dos factores, pero si estos son muy grandes, la operación puede exigir varios años de cómputo en un ordenador potente. Por ello se usan en el método RSA de encriptación de datos mediante claves públicas y privadas.
Profundizando algo más en el tema, con unos sencillos convenios se puede considerar que un número semiprimo nos da dos informaciones distintas de manera única. Por ejemplo, si convenimos en que cada número que recibamos por algún medio se considere como un producto de filas y columnas, con el número de filas no superior al de columnas, al recibir un número semiprimo podremos construir un rectángulo (una matriz) a partir de él de forma única.
Por ejemplo, si recibimos el número 91, lo podemos interpretar de forma única como el rectángulo 7*13. Es evidente que esto no ocurre con los demás números, como por ejemplo 63, que puede representar 7*9 o 3*21.
Esta propiedad permite transmitir ciertas informaciones de forma lineal simple. Si se recibe una serie de 35 dígitos como 27366524358291002738296634283912836, con el convenio anterior nos han enviado esta matriz:
2736652
4358291
0027382
9663428
3912836
jueves, 10 de diciembre de 2009
Teoría de las fracciones continuas
Si te han interesado los temas que hemos desarrollado (con la brevedad propia de un blog) sobre fracciones continuas, te ofrecemos un documento que expone la teoría de una forma sistemática y muy bien presentada.
Es un trabajo que nos ha enviado nuestro colaborador y amigo Rafael Parra Machío, que ya ha publicado comentarios muy interesantes en este blog.
Lo podéis descargar desde la dirección
http://www.hojamat.es/parra/fraccon.pdf
¡Buen aprendizaje!
Es un trabajo que nos ha enviado nuestro colaborador y amigo Rafael Parra Machío, que ya ha publicado comentarios muy interesantes en este blog.
Lo podéis descargar desde la dirección
http://www.hojamat.es/parra/fraccon.pdf
¡Buen aprendizaje!
viernes, 4 de diciembre de 2009
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
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
domingo, 4 de octubre de 2009
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
Pn = pn-1*an+pn-2
siendo an 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.
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
Pn = pn-1*an+pn-2
siendo an 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.
sábado, 5 de septiembre de 2009
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á)
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á)
Suscribirse a:
Entradas (Atom)