domingo, 25 de mayo de 2014

Sucesiones de Horadam - Soluciones enteras


Esta entrada participa en el Carnaval de Matemáticas 5.4, "Martin Gadner"

Durante este curso hemos venido estudiando sucesiones definidas mediante una recurrencia de segundo grado homogénea (sucesiones Horadam). Puede ser curioso estudiar estas sucesiones cuando las soluciones de la ecuación característica sean enteras.

Puedes repasar algo de este tipo de sucesiones en estas entradas que ya hemos publicado:

 http://hojaynumeros.blogspot.com.es/2014/01/recurrencias-lineales-de-segundo-orden.html

En ella se explican las recurrencias de segundo orden y cómo encontrar sus ecuación característica.

En estas otras explicamos ejemplos concretos, que te pueden servir de guía:

http://hojaynumeros.blogspot.com.es/2014/02/numeros-de-pell.html
http://hojaynumeros.blogspot.com.es/2014/01/sucesion-de-jacobsthal.html

Usaremos la misma herramienta de hoja de cálculo, recurre_lineal,  alojada en

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

Así que enlazaremos con lo ya publicado estudiando la ecuación característica x2-a1x-a2=0 en el caso en el que tenga soluciones enteras.

Es fácil ver que si llamamos Z1 y Za esas dos soluciones, deberá cumplirse que a1=Z1+Z2 y a2=-Z1Z2. Así de simple: si deseas unas soluciones determinadas (aquí enteras) basta que tomes como coeficiente de X(n-1) en la ecuación de recurrencia su suma y como segundo coeficiente su producto cambiado de signo:

X(n)=(Z1+Z2)X(n-1)-Z1Z2X(n-2)

Por ejemplo, si deseamos generar mediante recurrencia X(n)=5n-1n, el primer paso sería elegir como a1 su suma 6 y como  asu producto 5 tomado negativo.

Así de simple: si deseas unas soluciones determinadas (aquí enteras) basta que tomes como coeficiente de X(n-1) en la ecuación de recurrencia su suma y como segundo coeficiente su  su producto 5 tomado negativo:

X(n)=6X(n-1)-5X(n-2)

Los términos iniciales los elegiríamos por sustitución X(0)=50-10=1-1=0 y X(1)= 51-11=5-1=4. Lo volcamos todo en nuestra hoja de cálculo recurre_lineal y obtendremos:



Son los números de fórmula 5n-1 pedidos. Si resolvemos su ecuación característica comprobaremos esta expresión:



Esta sucesión la tienes en http://oeis.org/A024049 En la dirección http://oeis.org/wiki/Index_to_OEIS:_Section_Rec tienes un completo catálogo de sucesiones generadas de forma similar.

Situación inversa

Toda sucesión definida en su término general por X(n)=mAn+nBn (en este caso con m y n enteros) se puede generar de esta forma:

Si X(n)=mAn+nBn y X(n-1)=mAn-1+nBn-1, tendremos X(n+1)=(A+B)*(mAn+nBn)-AB*(mAn-1+nBn-1)= (A+B-B)*mAn+ (A+B-A)*nBn = mAn+1+nBn-1, luego la recurrencia es válida.

Después haríamos X(0)=m+n y X(1)=mA+nB

Toda sucesión del tipo X(n)=mAn+nBn se puede generar mediante una recurrencia lineal homogénea de segundo orden

Otro ejemplo

Tomemos otro ejemplo: X(n)=4n-2n. La recurrencia que la reproduce será: X(0)=0, X(1)=4-2=2, X(n)=6X(n-1)-8X(n-2)

Aquí tienes la sucesión formada con nuestra hoja de cálculo



Hemos elegido la recurrencia propuesta


Y hemos reproducido la diferencia de potencias como fórmula general:



Esta sucesión la tienes estudiada en http://oeis.org/A020522 y medio escondida figura la recurrencia.

De esta forma podemos generar cualquier otra sucesión de ese tipo. Tomemos un ejemplo con un negativo: X(n)=7n-(-2)n. En este caso tomaríamos X(0)=0, X(1)=9, X(n)=5X(n-1)+14X(n-2). En la imagen puedes estudiar la comprobación:



Función generatriz

Si una sucesión está definida como combinación lineal de potencias de dos enteros hemos demostrado que se puede generar mediante una recurrencia de segundo orden. Podremos usar el modelo de F.G. que definimos en su momento


En este caso se traduciría así:


En el ejemplo anterior se traduciría como


Lo comprobamos con PARI

{print(taylor(9*x/(1-5*x-14*x^2), x,12))}

Efectivamente, los coeficientes del desarrollo coinciden con los obtenidos con hoja de cálculo.

9*x + 45*x^2 + 351*x^3 + 2385*x^4 + 16839*x^5 + 117585*x^6 + 823671*x^7 + 5764545*x^8 + 40354119*x^9 + 282474225*x^10 + 1977328791*x^11 + O(x^12)

Números de Mersenne

Los números de forma 2n-1 son llamados “de Mersenne”, aunque son más populares los “primos de Mersenne” 3, 7, 31, 127, 8191, 131071,…Con lo explicado anteriormente será fácil generarlos:

 a1=3, a2=-2, X(0)=0, X(1)=1. Volcamos estos datos en la herramienta:



Obtenemos



Comprobamos la expresión general:



Estos números los encontrarás en http://oeis.org/A000225 Merece la pena que recorras los comentarios sobre esta sucesión, en especial su conexión con el problema de las torres de Hanoi.

En el apartado de fórmulas encontrarás la recurrencia que hemos usado y la función generatriz, que puedes comprobar con lo explicado anteriormente.

Una suma de potencias

¿Cómo engendrar mediante recurrencia la sucesión 2n+3n?

Te dejamos tan sólo el volcado de pantalla de la misma, para que saques tus consecuencias:





martes, 13 de mayo de 2014

Conjetura de Brocard y otras cuestiones

En una entrada de hace semanas ((http://hojaynumeros.blogspot.com.es/2014/04/comprobar-conjeturas-con-hoja-de.html) estudiamos la conjetura de Legendre:

Entre dos cuadrados consecutivos n2 y (n+1)2 existe siempre un número primo.

Se vio también una formulación alternativa:
Si usamos la función p, que da la distribución de los números primos (p(200) equivaldría a los primos que existen menores o iguales a 200), la conjetura de Legendre se podría expresar así:


Lo que no incluimos en esa entrada es que si n es un número primo mayor que 2, y estudiamos su cuadrado y el de su siguiente primo, entre ellos no existirá al menos un número primo, sino dos, porque entre los dos cuadrados existirá (salvo el caso de 2 y 3) otro cuadrado intermedio.

Resumiendo:

Para n>1, si representamos como p(n) al enésimo número primo, se verificará que entre p(n)2 y p(n+1)2 existirán al menos dos números primos.

Pues bien, Brocard propuso una conjetura más fuerte:

Conjetura de Brocard

Para n>1, si representamos como p(n) al enésimo número primo, se verificará que entre p(n)2 y p(n+1)2 existirán al menos cuatro números primos.

Podemos construir un modelo de hoja de cálculo para verificar esta conjetura para un número primo cualquiera. Usamos conjeturas.xlsm 
(http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2)
como en las entradas anteriores.



Elegimos un primo (en el ejemplo 2851) y con la función PRIMPROX le encontramos el siguiente debajo (2857). Mediante una fórmula condicional similar a “=SI(esprimo(F10);"Sí es primo";"No es primo")” comprobamos que efectivamente ambos son primos. A la derecha les calculamos sus cuadrados.

Para encontrar los cuatro primos comprendidos entre los cuadrados usamos de nuevo PRIMPROX. El primer primo de arriba será el PRIMPROX del primer cuadrado y los tres restantes serán los próximos primos de los de arriba.

Si el cuarto primo es menor que el segundo cuadrado (8128249<8162449), la conjetura queda comprobada para ese ejemplo. En caso contrario, corre a publicar el contraejemplo, que conseguirás la fama.

Como ocurría con la conjetura de Legendre, en la práctica no sólo existen cuatro primos, sino más. Los tienes publicados en http://oeis.org/A050216. Ahí verás que para n>1 los primos comprendidos son todos mayores que 4: 5, 6, 15, 9, 22, 11, 27, 47, 16, 57, 44, 20, 46, 80, 78, 32, 90, 66, 30, 106,…

Otras posibles situaciones

Nada nos impide plantear cuántos primos existen comprendidos entre dos elementos de cualquier sucesión creciente. Lo hemos estudiado entre cuadrados (Legendre) y entre cuadrados de primos (Brocard). Podíamos verlos entre triangulares consecutivos, por ejemplo. Este caso ya está estudiado y lo puedes consultar en http://oeis.org/A066888

Basta ver la sucesión para entender que se ha conjeturado que siempre existe al menos un número primo entre dos triangulares consecutivos para n>0: 0, 2, 1, 1, 2, 2, 1, 2, 3, 2, 2, 3, 3, 3, 3, 2, 4, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 4,…

Si recuerdas que la fórmula de un número triangular es n(n+1)/2, con ella y el uso de PRIMPROX podrás reproducir este esquema en hoja de cálculo:



De igual forma se pueden contar los comprendidos entre números oblongos (dobles de triangulares) consecutivos, n(n-1) y n(n+1) Los tienes en http://oeis.org/A108309 y parece lógico conjeturar que siempre existen dos primos entre cada par.

Otras sucesiones se pueden considerar, pero para que tengan interés es conveniente que las diferencias entre cada dos términos consecutivos no crezcan demasiado, lo que facilitaría la presencia de primos intermedios y quitaría interés a la cuestión. Sería el caso, por ejemplo, de las potencias de un número.

Se ha visto la cuestión con semiprimos en http://oeis.org/A088700  y con los términos de la sucesión de Fibonacci (http://oeis.org/A076777) y con seguridad en otros casos que no hemos buscado.

En este blog queremos aportar también nuestra particular sucesión con primos comprendidos. Probamos con los números poderosos

Primos entre poderosos

Llamamos número poderoso a aquél en el que todos sus factores primos presentan un exponente mayor que la unidad en la correspondiente descomposición factorial. Son poderosos 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, 144, 169,… http://oeis.org/A001694 En ellos, si un p primo divide a N, también lo divide su cuadrado, por lo que ninguno de ellos es libre de cuadrados. En virtud de esa definición se ha incluido el 1 en el listado. Por su forma de crecer parecen idóneos para contar primos entre ellos. Lo hemos hecho con este resultado:


Vemos que, por ejemplo, entre 100 y 108 se intercalan tres primos: 101, 103 y 107.
Si escribimos el listado de todas las diferencias observaremos la irregularidad de su distribución

2, 2, 0, 2, 3, 0, 2, 0, 4, 3, 2, 2, 3, 3, 2, 0, 1, 3, 5, 5, 2, 1, 1, 5, 1, 7, 0, 5, 2, 4, 5, 1, 5, 2, 7, 3, 2, 2, 6, 9, 4, 4, 0, 7, 8, 2, 7, 4, 4, 8, 1, 1, 4, 4, 9, 7, 2, 1, 9, 10, 6, 1, 0, 2, 0, 9, 12, 7, 4, 12, 6, 5, 4, 5, 12, 0, 8, 3, 3, 10, 8, 0, 2, 13, 2, 13, 10, 10, 1, 15, 0, 7, 9, 9, 3, 13, …

Los puedes buscar con PARI

ispowerful(n)={local(h);if(n==1,h=1,h=(vecmin(factor(n)[, 2])>1));return(h)}
proxpowerful(n)={local(k);k=n+1;while(!ispowerful(k),k+=1);return(k)}
{for(i=1,5000,if(ispowerful(i),m=proxpowerful(i);p=primepi(m)-primepi(i);print(p)))}

No dejan de aparecer ceros, aunque en general las diferencias parecen crecer.


Se asemejan a una vibración que no parara de crecer en amplitud. Como se ve, no hay lugar para una conjetura simple y elegante. Esto es lo normal, no va a resultar una conjetura en cualquier búsqueda que efectuemos.

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

En la parte inferior del gráfico se perciben los puntos de aquellos números poderosos consecutivos que no tienen primos intercalados entre ellos. Son estos:

8, 25, 32, 121, 288, 675, 1331, 1369, 1936, 2187, 2700, 3125, 5324, 6724, 9800, 10800, 12167, 15125, 32761, 39200, 48668… (sólo escribimos el primer elemento del par de poderosos)

Por ejemplo, entre el número poderoso 1331 y su siguiente 1352 no existe ni un solo primo.


Esta sucesión permanecía inédita y la hemos publicado en http://oeis.org/A240591

Su carácter creciente justifica que creamos que para un poderoso que no presente ningún primo entre él y el siguiente poderoso, existe otro mayor que él con la misma propiedad. La sucesión tendría infinitos términos.

Compuestos libres de cuadrados

Son números que no son primos y que no tienen divisores cuadrados salvo el 1. Estos dan mejor resultado que los poderosos, en el sentido de que las diferencias no oscilan tanto.



Aquí abundan los ceros y el resto de números presenta máximos que crecen lentamente. Por ejemplo, el primer par que posee tres primos intercalados es 346, que hasta el siguiente compuesto libre de cuadrados, el 354, presenta intercalados los primos 347, 349 y 353. Para llegar a cuatro primos intercalados hay que llegar nada menos que hasta 4584470.

1, 2, 0, 2, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 2, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 1…

Hemos usado este programa en PARI, además, como hacemos siempre, de una búsqueda previa con hoja de cálculo.

freesqrcomp(n)=issquarefree(n)&&!isprime(n)
nextfqc(n)={local(k);k=n+1;while(!freesqrcomp(k),k+=1);return(k)}
primesin(a,b)={local(p=a,q=0);while(p<b,p=nextprime(p);if(p<b,q+=1);p+=1);return(q)}
{for(i=2,100,if(freesqrcomp(i),m=nextfqc(i);p=primesin(i,m);print(i, " ",p)))}

Los hemos publicado en http://oeis.org/A240592

También podemos destacar aquí aquellos que no presentan primos en el intervalo respecto a su consecutivo. Son estos:

14, 21, 33, 34, 38, 55, 57, 62, 65, 69, 74, 77, 85, 86, 91, 93, 94, 105, 110, 114, 115, 118, 119, 122, 129, 133, 141, 142, 143, 145, 154, 158, 159, 165, 174, 177, 182, 183, 185, 186, 187, 194, 201, 202, 203, 205, 206, 209, 213, 214, 215,…

Su aparente tendencia a un crecimiento continuado nos hace pensar que la sucesión es indefinida y que siempre existirá otro elemento mayor que uno dado. (http://oeis.org/A240593)