lunes, 23 de febrero de 2015

Números especiales que son un producto especial (1)


Esta entrada y las siguientes tienen el doble objetivo de presentar unas curiosidades numéricas (algo intrascendentes) y analizar cómo organizar búsquedas de cierto tipo intentando dar con el algoritmo más rápido posible, ya que llegan fácilmente al orden de 10^7. Comenzamos con un ejemplo:

Números triangulares que son producto de triangulares

Muchos números triangulares son  producto de otros dos también triangulares. Por ejemplo, 45=15*3, 210=21*10, todos triangulares. Los tienes publicados en https://oeis.org/A188630

36, 45, 210, 630, 780, 990, 1540, 2850, 3570, 4095, 4851, 8778, 11781, 15400, 17955, 19110, 21528, 25200,…

Esta búsqueda está resuelta, pero imagina que la deseamos reproducir. No es fácil, porque para cada número natural deberíamos buscar lo siguiente:


  • Ver si ese número N es triangular
  • En caso afirmativo, recorrer todos sus divisores d.
  • Para cada uno de ellos, investigar si tanto d como N/d son ambos triangulares, y en caso afirmativo, parar la búsqueda para ese valor N y proseguir con N+1.

Es fácil darse cuenta de que se perderá mucho tiempo recorriendo números de uno en uno, que no son triangulares o bien que no poseen muchos divisores triangulares (o ninguno). Con  búsquedas de ese tipo, llamemos “ingenuas”, nuestro ordenador se pasaba minutos y minutos cuando llegaba a números grandes. Una solución es encaminar la búsqueda para que, hasta donde sea posible, sólo se recorran los números de cierto tipo. En el caso de triangulares, cuadrados, oblongos o primos, es posible realizar ese filtro. Lo concretamos:

Generación de triangulares

Los números que usaremos, salvo los primos, se pueden engendrar a partir de los precedentes.

Comenzaremos en esta entrada por explicar distintas formas de generar algunos tipos de números, y así ya las tenemos preparadas para cuestiones posteriores.

En el caso de los triangulares manejamos dos variables: Número N e incremento D. Comenzamos haciendo N=1 (primer triangular) e incremento D=2, para que 1+2 genere el siguiente triangular, el 3. Luego, en cada paso, N se convierte en N+D y D en D+1. Así funciona, ya que los números triangulares se forman añadiendo una fila con un elemento más.


Observa estos valores, generados con hoja de cálculo:



Recordamos: Los triangulares se generan tomando incrementos con una unidad más en cada paso. Ya utilizaremos esto más adelante.

Generación de cuadrados

Aquí tenemos dos soluciones, ambas prácticas, según el contexto, para recorrer sólo números cuadrados: la primera es trivial, declarar una variable k y luego usar k^2 en los cálculos. Está bien, pero a veces es lenta y no admite con facilidad ciertas acotaciones. La segunda es similar a la de los triangulares, pero incrementando D en D+2, en dos unidades en lugar de en una.


Observa el esquema:



Para quienes conozcáis estas propiedades, esto parecerá trivial, pero no está mal recordarlo, porque más adelante dará velocidad a nuestras búsquedas.

Generación de oblongos

Un número es oblongo cuando tiene la forma N=k(k+1), es decir, doble de un triangular. Es fácil ver que el siguiente oblongo será (k+1)(k+2). Su diferencia (k+1)(k+2)-k(k+1) = 2(k+1), es decir, el doble del mayor en el producto, luego el incremento adecuado será par y crecerá de 2 en 2. Esto nos permite generar oblongos: comenzamos con N=2 y D=4, Así generamos los siguientes: N=2+2*2=6, N=6+2*3=12, N=12+2*4=20,…También podemos declarar una variable y después trabajar con k*(k+1). Así hemos procedido en nuestra primera búsqueda con hojas de cálculo.



Así que, mientras los cuadrados se generan sumando impares, los oblongos sumando pares (y los triangulares sumando todos)

Caracterización de estos números

Necesitaremos también en las búsquedas que emprenderemos una forma de caracterizar estos números, cómo saber si un resultado es cuadrado u oblongo, por ejemplo. Aunque es sencillo y conocido, lo recordamos aquí:

Para saber si un número natural es cuadrado, la mejor prueba es que la parte entera de su raíz cuadrada, elevada a su vez al cuadrado, nos dé como resultado el número primitivo. En hoja de cálculo:

Public Function escuad(n) As Boolean
If n < 0 Then
escuad = False
Else
If n = Int(Sqr(n)) ^ 2 Then escuad = True Else escuad = False
End If
End Function

Si trabajas con las celdas, sin macros, el procedimiento es el mismo, pero con distinto lenguaje. Si tienes, por ejemplo, en la celda C12, un número del que deseas saber si es cuadrado, escribe en otra celda esta fórmula: =SI((ENTERO(RAIZ(C12)))^2=C12;1;0), y te devolverá un 1 si es cuadrado y un 0 si no lo es.

La caracterización de un número como triangular se basa en lo anterior, ya que ser triangular N es equivalente a que 8*N+1 sea cuadrado. Por tanto, podemos definir esta función:

Function estriangular(n) As Boolean
If escuad(8 * n + 1) Then estriangular = True Else estriangular = False
End Function

En lenguaje de celdas sería algo más complejo:
=SI((ENTERO(RAIZ(C12*8+1)))^2=C12*8+1;1;0),
Por último, los oblongos, al ser doble de triangulares, se descubren fácilmente:

Public Function esoblongo(n) As Boolean
If escuad(4 * n + 1) Then esoblongo = True Else esoblongo = False
End Function

Sin macros, =SI((ENTERO(RAIZ(C12*4+1)))^2=C12*4+1;1;0)

Algoritmos de búsqueda

Ya podemos pasar a nuestras búsquedas. Comenzaremos generando la sucesión https://oeis.org/A188630, con la que comenzamos esta entrada: Números triangulares que son producto de otros dos triangulares.

Nos organizaremos así:

Iniciamos triangulares: N=3, D=3 (Comenzamos por el 3)
1 Mientras no lleguemos al tope que nos hayamos marcado
    Iniciamos otros triangulares para ver si son divisores: K=3, P=3 
      2 Mientras no lleguemos a N ni encontremos un producto de triangulares
         Para cada K vemos si:
         1.-Es divisor de N
         2.- Si el cociente N/k es triangular
         Si cumple ambas condiciones, cerramos la búsqueda para N e imprimimos.
         Si no, generamos otro triangular convirtiendo K en K+P y P en P+1
     Fin de 2 Mientras
  Generamos otro triangular convirtiendo N en N+D y D en D+1
Fin del 1 Mientras

 Hemos comenzado los triangulares en el 3 para evitar trivialidades.

Para quienes no manejen mucho los algoritmos puede resultar complicado, pero hay que repasar hasta entenderlo. Se puede traducir al Visual Basic de Excel:

Sub productriang()
Dim i, j, k, p, c
i = 3: j = 3 Iniciamos la búsqueda en 3, para eliminar trivialidades
While i <= 10 ^ 4
k = 3: p = 3: c = 0 También iniciamos los divisores en 3
While c = 0 And p < i
If i / k = i \ k And estriangular(i / k) And i / k > 1 Then c = k
En la línea anterior buscamos que sea divisor, cociente triangular y no trivial
If c <> 0 Then MsgBox (i) Si cumple todo, presentamos el resultado
k = k + p: p = p + 1 Generamos el siguiente divisor
Wend
i = i + j: j = j + 1 Generamos el siguiente triangular
Wend
End Sub

Elimina comentarios, copia el resto como rutina para Visual Basic y al ejecutar verás aparecer los valores 36, 45, 210,…

Si te apetece explorar, aquí tienes la versión para PARI

{i=3;j=3; Iniciamos la búsqueda en 3, para eliminar trivialidades
while(i<=10^4,k=3;p=3;c=0; También iniciamos los divisores en 3
while(k<i&&c==0,if(i/k==i\k&&ispolygonal(i/k,3)&&i/k>1,c=k);
En la línea anterior buscamos que sea divisor, cociente triangular y no trivial
if(c>0,print1(i,", ")); Si cumple todo, imprimimos
k+=p;p+=1); Generamos el siguiente divisor
i+=j;j+=1) Generamos el siguiente triangular
}

Igualmente, si eliminas los comentarios y ejecutas este código PARI verás reproducida la sucesión https://oeis.org/A188630



Nos hemos detenido mucho en la generación de algunos tipos de números, su caracterización  y en la estructura general del algoritmo de búsqueda, pero en las siguientes entradas nos servirá todo esto para entender mejor los procesos.