viernes, 27 de febrero de 2015

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


Números triangulares como producto de otros 

En la entrada anterior planteamos el problema de buscar los números triangulares que son a su vez producto de otros dos triangulares. Presentamos una forma de generar cuadrados, oblongos y triangulares de la forma más rápida posible, ya que estas búsquedas se hacen lentas para números grandes, y construimos un algoritmo para generar estos números, contenidos en la sucesión de OEIS https://oeis.org/A188630

En esta entrada generaremos triangulares con otros tipos de números, y llegaremos a sucesiones que permanecían inéditas hasta ahora.

Triangulares producto de dos cuadrados

Aquí no hay que buscar mucho, ya que basta considerar que el número que cumple esto es aquel que es cuadrado (producto de cuadrados) y triangular a la vez. Esto está muy estudiado. Son estos:

1, 36, 1225, 41616, 1413721, 48024900, 1631432881,… y está publicados en https://oeis.org/A001110

Vemos, pues, otros casos.

Triangulares que son producto de un triangular y un cuadrado

Ahora tenemos ocasión de aplicar lo expuesto en la entrada anterior: cómo generar de forma rápida cuadrados y triangulares y cómo saber si son o no de ese tipo. Si esto te quedó claro, entenderás el algoritmo que sigue. Primero en Visual Basic de Excel:

Sub productriang()
Dim i, j, k, p, c
i = 3: j = 3 Generamos el primer triangular
While i <= 10 ^ 4
k = 3: p = 3: c = 0 Aquí generamos posibles divisores triangulares
While c = 0 And p < i  Cuando c<>0 se para la búsqueda y se comunica el resultado
If i / k = i \ k And escuad(i / k) And i / k > 1 Then c = k
La línea de arriba investiga si k es divisor y si i/k es cuadrado
If c <> 0 Then MsgBox (i)
k = k + p: p = p + 1  Genera el siguiente posible divisor triangular
Wend
i = i + j: j = j + 1  Genera el siguiente triangular para seguir buscando
Wend
End Sub

Si repasas la entrada anterior, es el mismo algoritmo propuesto en ella, pero cambiando estriangular(i/k) por escuad(i/k). Puedes repasar los comentarios que se incluían. Con un ligero cambio en el código, hemos situado los resultados en columna:


A partir de este valor se produce desbordamiento, por lo que acudimos a PARI y al código

{i=3;j=3;
while(i<=10^6,k=3;p=3;c=0;
while(k<i&&c==0,if(i/k==i\k&&issquare(i/k)&&i/k>1,c=k);
if(c>0,print1(i,", "));
k+=p;p+=1);
i+=j;j+=1)
}
No insertamos comentarios porque es el mismo que presentamos en la entrada anterior, salvo el uso de la función issquare (“es cuadrado”)

Con él puedes obtener los primeros números triangulares que son producto de un triangular y un cuadrado:


300, 1176, 3240, 7260, 14196, 25200, 29403, 41616, 64980, 97020, 139656, 195000, 228150, 265356, 353220, 461280, 592416, 749700, 936396, 1043290, 1155960, 1412040, 1708476, 2049300, 2438736, 2881200, 3381300, 3499335, 3943836, 4573800,…

Esta sucesión no se había publicado, y lo hicimos en http://oeis.org/A253650

Si los escribimos en columna podemos desarrollarlos como producto del tipo deseado:



Antes de seguir adelante, hay que advertir que estas descomposiciones en producto no tienen que ser únicas. Por ejemplo, 2881200 admite estos dos productos: 3*960400 y 300*9604, ambos formados por un triangular y un cuadrado. Por eso en la tabla se puede tener la falsa idea de que el factor triangular es más pequeño que el cuadrado. No es así, sino que hemos detenido la búsqueda al encontrar un ejemplo.

Una curiosidad

Los números triangulares de esta sucesión, tendrán, como todos la forma T(P)=P(P+1)/2. Pues bien, ni P ni P+1 pueden ser primos, porque si se descompone en un producto de un triangular y un cuadrado, tendríamos P(P+1)=k(k+1)m2 y si P o P+1 fueran primos, tendrían que dividir a k o a k+1 o a m, y los tres son menores que P. Estúdialo. Lo vemos en una tabla con los primeros casos:



Subconjunto interesante

Los números triangulares de orden k2-1, siendo k impar y mayor que 1, pertenecen a esta sucesión. En efecto, si k es impar tendrá la forma 2m+1, luego el orden del triangular será

 (2m+1)2-1=4m2+4m.

El triangular formado sobre él tendrá la forma (((2m+1)2*(4m2+4m)/2 y se puede descomponer en un cuadrado y un triangular: 4((2m+1)2 * m(m+1)/2.

Otra forma de expresarlo es que son triangulares construidos sobre 8 veces otro número triangular, ya que 4m2+4m=8*(m(m+1)/2). Estos números los tienes en http://oeis.org/A185096

Casi todos los elementos de la sucesión tienen esta forma: 300, 1176, 3240, 7260, 14196, 25200,… y pertenecen a la sucesión http://oeis.org/A083374 pero otros no, como 29403, 1043290 y 3499335.

Triangulares que son producto de un triangular y un primo

En esta búsqueda nos organizaremos de forma similar a la precedente pero al llegar a investigar si (i/k) es cuadrado o triangular, deberemos sustituirlo por la pregunta de si es primo. Esta es más difícil de responder, pero disponemos de la función isprime en PARI y de esprimo en nuestra hoja Conjeturas (http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global)

Puedes adaptar el algoritmo usado en la búsqueda anterior cambiando esas funciones: Observa que ahora, con lo explicado antes, las operaciones se entienden mejor, por lo que omitimos los comentarios y usamos color rojo en las novedades. Para hoja de cálculo podría servir esta rutina de Visual Basic:

Sub productriang()
Dim i, j, k, p, c


i = 3: j = 3
While i <= 10 ^ 3
k = 3: p = 3: c = 0
While c = 0 And p < i
If i / k = i \ k And esprimo(i / k) And i / k > 1 Then c = k
If c <> 0 Then MsgBox (i)
k = k + p: p = p + 1
Wend
i = i + j: j = j + 1
Wend
End Sub

En PARI

{i=3;j=3;while(i<=10^6,k=3;p=3;c=0;while(k<i&&c==0,if(i/k==i\k&&isprime(i/k)&&i/k>1,c=k);if(c>0,print1(i,", "));k+=p;p+=1);i+=j;j+=1)}

Los triangulares obtenidos son, en este caso, los siguientes:

6, 15, 21, 45, 66, 78, 105, 190, 210, 231, 435, 465, 630, 861, 903, 1035, 1326, 2415, 2556, 2628, 3003, 3570, 4005, 4950, 5460, 5565, 5995, 7140, 8646, 8778, 9870, 12246, 16471, 16836, 17205, 17391, 17766, 20100, 22155, 26565, 26796, 28680, 28920, 30381, 32131, 33411, 33930, 36856, 40755,… (los publicamos en http://oeis.org/A253651)

Podíamos pensar que, al ser el segundo factor primo, el primero será el máximo divisor triangular propio que tiene el número que se descompone
 (ver http://hojaynumeros.blogspot.com.es/2013/02/de-los-triangulares-alojados-los-primos.html).

Esto es así en la gran mayoría de casos. Así, 4005 se descompone como 45*89, siendo 45 es el máximo divisor triangular propio de 4005 y 89 un factor primo. Sin embargo, en el número 3570, su divisor triangular máximo es 595, que daría lugar al producto 3570=595*6, y el 6 no es primo. El producto válido sería 3570=210*17, que sí es primo.

Triangulares producto de triangular y oblongo

Estos son los primeros:

6, 36, 120, 210, 300, 630, 1176, 2016, 3240, 3570, 4950, 7140, 7260, 10296, 14196, 19110, 23436, 25200, 32640, 39060, 41616, 52326, 61776, 64980, 79800, 97020, 116886, 139656, 145530, 165600, 195000, 228150, 242556, 265356, 304590, 306936, 349866, 353220, 404550, 426426, …

Si recuerdas la caracterización de los oblongos en la entrada anterior, entenderás este código en PARI:

{i=3;j=3;
while(i<=10^6,k=2;p=4;c=0;
while(k<i&&c==0,if(i/k==i\k&&issquare(4*(i/k)+1)&&i/k>1,c=k);
if(c>0,write1("final.txt",i,", "));
k+=p;p+=2);
i+=j;j+=1)
}

Destacamos que el doble de cualquiera de estos números tiene la forma N=P(P+1)Q(Q+1).  Así, 2*2016=4032=7*8*8*9. Al contrario, como uno de los factores es oblongo, el producto será par y se podrá dividir entre dos y su mitad será producto de dos triangulares.

Todos los términos no nulos de la sucesión A083374 (6, 36, 120, 300, 630, 1176, 2016, 3240,…) pertenecen a esta, pues si tienen la forma n2(n2-1)/2 se pueden descomponer en el oblongo n(n+1) y el triangular n(n-1)/2, o bien el oblongo n(n-1) y el triangular n(n+1)/2.

Hemos publicado esta sucesión en http://oeis.org/A253652

Triangulares producto de un cuadrado y un primo

Al llegar a este punto simplificamos la exposición, ya que tendrás una buena idea de cómo se generan. Los triangulares que se forman multiplicando un cuadrado y un primo son estos:

28, 45, 153, 171, 300, 325, 496, 2556, 2628, 3321, 4753, 4851, 7381, 8128, 13203, 19900, 25200, 25425, 29161, 29403, 56953, 64980, 65341, 101025, 166753, 195625, 209628, 320400, 354061, 388521, 389403, 468028, 662976, 664128, 749700, 750925, 780625, 781875, 936396,…

Los números perfectos lo cumplen

Entre los números encontrados figuran los perfectos 28, 496, 8128,… https://oeis.org/A000396
La razón es que estos números tienen la forma 2k-1(2k-1)= 2k(2k-1)/2, y son, por tanto, triangulares. Además, como (2k-1) es primo de Mersenne en esta expresión, k ha de ser impar, y k-1, par, con lo que 2k-1 es un cuadrado y (2k-1) un primo, cumpliéndose así la condición.

Para no cansar más con este tema, sólo incluimos el código PARI con las novedades en rojo:

PARI
{i=3;j=3;
while(i<=10^6,k=4;p=5;c=0;
while(k<i&&c==0,if(i/k==i\k&&isprime(i/k)&&i/k>1,c=k);
if(c>0,write1("final.txt",i,", "));
k+=p;p+=2);
i+=j;j+=1)
}

Pues ya está bien. Ahora te toca a ti. ¿Sabrías prolongar las siguientes sucesiones con las técnicas que hemos desarrollado en las dos entradas?:

Triangulares producto de un cuadrado y un oblongo: 120, 300, 378, 528, 990, 1176, 2016,…

Y por último, los triangulares producto de un oblongo y un primo: 6, 10, 36, 66, 78, 210, 276, …


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.

lunes, 16 de febrero de 2015

Números “Tribonacci”


Los números “tribonacci” son análogos a los de Fibonacci, pero generados mediante recurrencias de tercer orden homogéneas.  Existen muchas sucesiones con este nombre, según sean sus condiciones iniciales. Aquí comenzaremos con la contenida en

http://mathworld.wolfram.com/TribonacciNumber.html

pero podemos cambiar más tarde si surgen propiedades interesantes para su estudio con hoja de cálculo.

En estos números la fórmula de recurrencia posee todos sus coeficientes iguales a la unidad

xn= A*xn-1+B*xn-2+C*xn-3 se convertiría en

xn= xn-1+xn-2+xn-3

Al igual que en el caso de Fibonacci, los dos valores iniciales también valen 1, y el tercero, 2, pero ya hemos explicado que existen otras variantes. Dejamos los enlaces de algunas de ellas:

http://oeis.org/A000073  comienza con a(0)=a(1)=0, a(2)=1
http://oeis.org/A000213  con a(0)=a(1)=a(2)=1
http://oeis.org/A001590 con a(0)=0, a(1)=1, a(2)=0
http://oeis.org/A081172 comienza con 1,1,0.

Y hay más.

Como ya hemos indicado, nosotros comenzaremos con:

Condiciones iniciales: x0=1, x1=1x2=2 Ecuación de recurrencia: xn= xn-1+xn-2+xn-3

Los primeros términos son:

 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744,… http://oeis.org/A000073

Como en otras entradas sobre el mismo tema, podemos acudir a nuestra herramienta de hoja de cálculo para sucesiones recurrentes

http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2

En la imagen puedes identificar los coeficientes y valores iniciales



Con el botón “Ver sucesión” podremos obtener el listado de estos números:


Ecuación característica

Al igual que en otras sucesiones recurrentes, su ecuación característica se formará a partir de sus coeficientes, en este caso todos iguales a 1, luego será x3-x2-x-1=0

Con nuestra herramienta podemos encontrar sus raíces:



La misma solución obtenemos con WxMaxima



Recordemos que los elementos de las sucesiones recurrentes se pueden expresar como suma de potencias de las tres soluciones, pero con estos números ocurre como con algunos similares (los de Fibonacci, Perrin o Narayana), y es que las raíces complejas, al tener módulo inferior a la unidad, tienden a cero si prolongamos la sucesión. Por ello, las potencias de la raíz real, 1,839286…generan con bastante aproximación los números Tribonacci, y, lo que es lo mismo, esta constante coincidirá aproximadamente con el cociente entre dos de estos números consecutivos. Lo vemos con hoja de cálculo:



Por ello, al número 1,839286…se le llama Constante Tribonacci.

Función generatriz

Todas las variantes de las sucesiones Tribonacci comparten los mismos coeficientes de recurrencia, y por tanto también el denominador de su función generatriz. La que estamos estudiando en esta entrada, de inicio 1, 1, 2, se genera con la siguiente:


Al igual que con otras sucesiones, la comprobaremos con PARI:

write("sucesion.txt",taylor((x)/(1-x-x^2-x^3),x,20))

Te escribirá en un archivo sucesión.txt su desarrollo (este archivo lo deberás tener vacío en la misma carpeta que PARI), y aparecerán como coeficientes los términos de la sucesión Tribonacci:

x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 13*x^6 + 24*x^7 + 44*x^8 + 81*x^9 + 149*x^10 + 274*x^11 + 504*x^12 + 927*x^13 + 1705*x^14 + 3136*x^15 + 5768*x^16 + 10609*x^17 + 19513*x^18 + 35890*x^19 + O(x^20)

Una excursión por la hoja de cálculo

Podemos usar la versión matricial de la generación de estos números para recordar algunos detalles sobre hojas de cálculo.

Es elemental comprobar que las ternas de números consecutivos de Tribonacci. T(n), T(n+1), T(n+2) pueden engendrar matricialmente la terna siguiente T(n+1), T(n+2), T(n+3), mediante la siguiente fórmula matricial:


Esta fórmula es adecuada para repasar las fórmulas matriciales de las hojas de cálculo. Comenzamos construyendo un esquema como el de la imagen:



Para efectuar el producto matrical deberemos usar la función MMULTI, con parámetros la primera matriz y la columna de la primera terna:

{=MMULT(D4:F6;H4:H6)}

Observa que como multiplicamos rangos de celdas, usamos el separador :

Para que la hoja entienda que se trata de una multiplicación matricial, cuando termines de escribir la fórmula, en lugar de terminar con INTRO, usaremos Ctrl+Mayúscula+INTRO. La aparición de las llaves es la señal de que la fórmula ha sido introducida correctamente.

Una vez efectuado el cálculo sobre una terna, basta que copies el resultado como dato, usando Copiar y Pegado especial como valores, y proseguirán apareciendo ternas nuevas.

Uno de los autovalores de la matriz que hemos usado es la constante de Tribonacci, 1,839286…La razón es que el polinomio característico de la matriz es el mismo que el de la ecuación característica de la recurrencia, x3-x2-x-1=0.

Curiosidades

En esta serie sobre sucesiones recurrentes solemos presentar en cada una de ellas propiedades curiosas, no todas las conocidas, que llenarían libros, sino las que más nos llamen la atención o se adapten mejor a las herramientas que usamos. Para la de Tribonacci presentaremos una propiedad combinatoria.

Particiones de un número en sumandos no mayores que 3

Los números de Tribonacci (salvo los iniciales) cumplen que T(N) coincide con las particiones de N-1 en sumandos que se pueden repetir, en cualquier orden y con los sumandos menores o iguales a 3. Por ejemplo, T(5)=7, que coincide con las particiones del número 4 en partes no superiores a 3:
Lo comprobamos con el listado obtenido con nuestra hoja no publicada “Cartesius”:



Observamos que resultan 7 particiones distintas.

Para T(4)=4 obtenemos el mismo resultado con particiones del número 3:


La razón de que esto funcione así es que cualquier partición de este tipo con N elementos ha resultado a adjuntar un 1 a las particiones de N-1, un 2 a las de N-2 y un 3 a las de N-3, con los que se cumple xn= xn-1+xn-2+xn-3 . Para que lo entiendas mejor hemos coloreado estos tres sumandos para el caso de T(6)=13:





lunes, 9 de febrero de 2015

Conjetura de Polignac


Se llama Conjetura de Polignac a la enunciada por Alphonse de Polignac in 1849 y que se puede expresar así:

Hay un número infinito de números primos (p, q) tales que p - q = k, siendo k un número par.

Últimamente se ha hablado más de ella por algunos avances que se han producido y que pudieran llevar a su demostración

(Ver http://gaussianos.com/de-70000000-700-en-seis-meses/ y http://en.wikipedia.org/wiki/Polignac%27s_conjecture)

Dentro de esta conjetura, y para k=2 se incluye la de los primos gemelos:

Existen infinitos pares de primos gemelos (p, p+2)

(http://es.wikipedia.org/wiki/Conjetura_de_los_n%C3%BAmeros_primos_gemelos)
Pero también podríamos expresar lo mismo para pares del tipo (p, p+4), “cousin primes” y los del tipo (p, p+6), “sexy primes”.

Nosotros trabajaremos con el enunciado general, sobre los pares (p, p+k), con k número par. Para ello, usaremos el valor de k como entrada a algoritmos de búsqueda.

Esquema sin macros

Para buscar estos pares (p, p+k) ambos primos podemos crear en la hoja Conjeturas (http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global) una lista de números primos p en forma de columna. Para ello la iniciamos con el número que deseemos, generalmente grande, y después, en cada fila usamos la función PRIMPROX(N), siendo N el número contenido en la celda de arriba, con lo que para aumentar la lista bastará extender la fórmula hacia abajo. Después creamos una columna paralela formada por p+k. Por último, en una tercera columna usamos la función ESPRIMO. De esta forma, la aparición del primer par con ambos primos se detectará por el valor VERDADERO de esa función.

En la imagen hemos detectado el primer par de números gemelos después del número 1000000, el (1000037,1000039), Se comprende que si la conjetura es verdadera, prolongando las columnas lo que sea necesario, encontraremos un par de primos con la diferencia que hayamos fijado.



Por ejemplo, aquí tienes los primeros primos diferenciados en 1000 que siguen a 10000000:



La columna puede hacerse muy alta, y nos convendría también poder encontrar los pares buscados con una sola función.

Función Polignac

Para abreviar el proceso usaremos la función POLIGNAC(P;K), que hemos añadido a nuestra hoja cálculo conjeturas, enlazada más arriba.

Esta función actúa sobre un inicio n y una diferencia par k, y encuentra el primer número primo p posterior al inicio que forma par de primos con p+k. Basta leer los comentarios para entender su funcionamiento.

Function polignac(n, k)
Dim novale As Boolean
Dim p, q

p = n ‘Iniciamos la búsqueda en n
novale = True ‘Variable para terminar la búsqueda
If k / 2 <> k \ 2 Then polignac = 0: Exit Function ‘Si k es impar, damos valor 0 a la función
While novale
p = primprox(p) ‘Buscamos el siguiente primo
If  esprimo(p + k) Then q = p: novale = False ‘Si encontramos (p,p+k) paramos
Wend
polignac = q ‘Damos a la función el valor del primer primo del par
End Function

Por ejemplo, deseamos comprobar la conjetura encontrando el primer par de números primos diferenciados en 2000 que sigue al inicio 10^6. En la imagen, capturada de la hoja conjeturas.xslm tienes la respuesta: 1000121 es el primer primo tal que al sumarle 2000 se obtiene otro primo 1002121. El resto del esquema lo hemos organizado para que se obtengan varios pares en lugar de uno solo. A la derecha hemos incluido la prueba de que ambos son primos. Te invitamos a que construyas un esquema similar en la hoja conjeturas.


Como en todas las cuestiones, la hoja de cálculo puede fallar para números muy grandes, por lo que debemos acudir a programas más potentes. Elegimos PARI por ser gratuito. Podemos usar la siguiente función, a la que hemos añadido un “print” para que veas el resultado:

polignac(n,k)={local(p);p=nextprime(n);while(!isprime(p+k),p=nextprime(p+1)); return(p)}
{print(polignac(10^6,2000))}

Si lo ejecutas obtendrás el mismo número primo que con la hoja, 1000121:



También aquí puede fallar la función para números muy grandes, pero el margen es mayor que en Excel.

La idea es que si la conjetura es cierta (y la herramienta de cálculo lo admite), podemos elegir un número de inicio arbitrariamente grande y siempre tendremos un resultado.

Lista de números primos gemelos, “cousin”, “sexy” y otros

Con esta función puedes crearte fácilmente una lista de primos gemelos. Basta usarla de forma recurrente en columna a partir del 1, y con una diferencia dada. En el esquema que adjuntamos más arriba usamos esta técnica:



El primer par de primos gemelos (3,5) se ha construido a partir del 1. Los siguientes, a partir del anterior, con la función polignac(p,k). Las columna de la derecha la programamos para que sume el valor de k a la de la izquierda.

Si la conjetura de Polignac es cierta, esta tabla tendría una altura infinita. No terminarían de aparecer pares.

Podemos construir de esta forma los pares de primos “cousin”, que se diferencian en 4.



De igual forma, los “sexy”:



Nada nos impide crear una lista personalizada. Por ejemplo, si has nacido en el año 1962, como es par, puedes crear pares de primos con esa diferencia:



Llama la atención que el primer elemento del par no tiene que ser muy grande aunque k lo sea. Observa la lista de pares con una diferencia de 1000000:



Otras posibilidades

No podemos construir tríos de primos de este tipo, porque siempre uno de ellos sería múltiplo de 3, pero sí tríos de la forma (p, p+2, p+6), o, en general (p, p+k, p+3k). Para explorar un poco por este camino, bastaría sustituir la línea de Basic

If  esprimo(p + k) Then q = p: novale = False 

Por esta otra

If esprimo(p + k) And esprimo(p + 3 * k) Then q = p: novale = False

Si la conjetrura de Polignac es cierta, estas búsquedas terminarán por dar un resultado. Observa el caso de n=1000000 y k=1000


Casi todos estos casos están publicados y no pasan de ser curiosidades derivadas de la conjetura que estudiamos. Si eliges un ejemplo inadecuado, como (p, p+2, p+4), puede ocurrirte que se bloquee la hoja de cálculo y tengas que recurrir al Administrador de tareas para cerrarla.

Por el contrario, si consigues tríos no publicados, podrías intentar incluirlos en OEIS.