jueves, 24 de diciembre de 2009

Suma de tres números triangulares

En 1796, Gauss descubrió que todo entero positivo puede representarse como la suma de un máximo de tres números triangulares. Estos pueden ser iguales, y si consideráramos el 0 como triangular, podríamos afirmar que todo número natural es suma de tres triangulares.

Un ejercicio interesante es el de descubrir un algoritmo que los encuentre. Para hacerlo más formativo podemos basarnos en dos funciones, una para descubrir si un número es triangular y otra que nos devuelve el mayor triangular mayor o igual que un número dado.

Función estriangular
Si un número N es triangular verificará igualdad N=x(x+1)/2, con x y N ambos enteros, lo que obliga a que 8*N+1 sea cuadrado perfecto ¿por qué?. Esto nos lleva a este código:

Public function estriangular(n) as boolean
dim a

a = Int(sqr(8*n+1))

if a*a=8*n+1 then estriangular = true else estriangular = false
end function

Función mayortriang

Para encontrar el mayor triangular contenido en un número N bastará resolver la ecuación N=x(x+1)/2 truncando el resultado a un número entero. Así que quedará:

Public Function mayortriang(n)
dim a
a = Int((sqr(8*n+1)-1)/2)
mayortriang=a*(a+1)/2

end function


Con esto ya tenemos preparado un algoritmo para OpenOffice.org Calc (fácilmente adaptable a Excel) que encuentre todas las descomposiciones en tres triangulares (incluido el cero):

Sub sumatriangulares
Dim i,j,k

dim a,b
i=StarDesktop.CurrentComponent.sheets(0).GetCellByPosition(3,3).value (se supone que el número se escribe en la celda D4)
a=mayortriang(i)
for j=0 to a (se recorren los valores posibles del primer sumando)
if estriangular(j) then
b=mayortriang(i-j)

for k=j to b
(se recorren los valores posibles del segundo sumando)
if estriangular(k) then
if estriangular(i-j-k) and i-j-k>=k then (el tercer sumando ha de ser triangular)
msgbox(j) (se presenta el resultado)
msgbox(k)

msgbox(i-j-k)
end if

end if

next k

end if
next j

End Sub


Pues ánimo y a implementarlo. Puedes añadir una variable que cuente todas las formas de descomposición que tiene un número. Por ejemplo, entre los de tres cifras hay uno que admite 24 sumas distintas de triangulares ¿Cuál?

sábado, 19 de diciembre de 2009

Primos, semiprimos y casi primos (3)

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

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.

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

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!

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