martes, 29 de abril de 2014

Números de Lucas

Esta entrada participa en la Edición 5.3: Felix Klein del Carnaval de Matemáticas cuyo anfitrión es Juegos Topológicos.


En entradas anteriores hemos estudiado algunas sucesiones tipo Horadam. Son aquellas que se forman mediante una recurrencia lineal de segundo orden homogénea, es decir del tipo xn=a1xn-1+a2xn-2
(http://mathworld.wolfram.com/LinearRecurrenceEquation.html)

Interpretamos que cada término a partir uno de ellos equivale al anterior multiplicado por un número más el anterior del anterior por otro. A esos dos números a1 y a2 les llamaremos los coeficientes de la recurrencia.

Lo normal es definir directamente los primeros términos, llamados valores iniciales, y después dar los coeficientes de la recurrencia, que supondremos constantes. Por ejemplo, en la sucesión de Fibonacci, definimos directamente x0=1, x1=1 y usamos los coeficientes a1=1 y a2=1, con lo que la relación de recurrencia vendrá dada por xn=xn-1+xn-2, constituyendo una recurrencia lineal de segundo orden homogénea, y entrando así en nuestro estudio.

Estas sucesiones reciben el nombre de “sucesiones de Horadam” y se caracterizan por estar determinadas por esos cuatro parámetros dentro de una recurrencia de segundo orden homogénea. Así, la sucesión de Fibonacci es Horadam(0,1,1,1), porque los parámetros se escriben en orden inverso a como lo hacemos aquí. Sólo estudiaremos algunos casos, pues el tema es muy amplio y con muchas sucesiones interesantes.  En este enlace puedes repasar el funcionamiento de una herramienta para estudiarlas:

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

En estas entradas se estudiaron dos casos concretos

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

La herramienta de hoja de cálculo la tienes en

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


Sucesiones de Fibonacci generalizadas

Se han estudiado mucho las sucesiones de Horadam con coeficientes A=1 y B=1. Algunas de ellas son muy populares, formando un pequeño entramado de sucesiones similares que tendremos que desentrañar. Comencemos dando a X0 y X1 los valores usuales entre 0 y 2:

X0=0 y X1=1: Resulta la sucesión de Fibonacci comenzando en 0: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,… http://oeis.org/A000045. Por  ahora no la estudiaremos. Se ha escrito tanto sobre ella que no parece fácil aportar algo nuevo.

X0=1 y X1=1: Resulta la sucesión de Fibonacci comenzando en :  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…La nombraremos como F(n) http://oeis.org/A000045

X0=1 y X1=2: Se formará la misma sucesión comenzando en el segundo 1:  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

X0=2 y X1=1: Obtenemos la sucesión de Lucas comenzando en 2: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571,… http://oeis.org/A000032. La representaremos como L(n)

X0=1 y X1=3: Obtenemos la sucesión de Lucas comenzando en 1: 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571,… http://oeis.org/A000204

Nos detenemos aquí: según los términos iniciales, podemos obtener la clásica sucesión de Fibonacci, la de Lucas o la de otras del tipo Fibonacci, como la contenida en http://oeis.org/A104449

No nos cabrían aquí todas las propiedades de la primera, ya muy estudiadas y publicadas. Sólo destacaremos alguna de ellas si lo vemos oportuno y nos dedicaremos más a los números de Lucas.

Números de Lucas

Los números de Lucas se pueden engendrar con los coeficientes A=1 y B=1 comenzando con X0=2 y X1=1  (más arriba hemos visto otra variante), es decir forman la sucesión de Horadam(2,1,1,1).

En estas direcciones puedes ampliar el tema:

http://www.librosmaravillosos.com/circomatematico/capitulo13.html
http://gaussianos.com/algunas-curiosidades-sobre-los-numeros-de-fibonacci/
http://mathworld.wolfram.com/LucasNumber.html

 Con hoja de cálculo y nuestra herramienta recurre_lineal presentan estos valores:



2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571,… Los representaremos como L(n) http://oeis.org/A000032

En la parte derecha, que te da automáticamente la expresión respecto a n, puedes comprobar la fórmula de L(n)

Es parecida a la de la sucesión de Fibonacci, con la que comparte la misma fórmula de recurrencia. Observa que a partir de n=2, el valor absoluto de la segunda potencia es menor que ½, por lo que X(n) coincidirá con la parte entera de la primera, que coincide con la razón áurea j elevada a n. Es decir:
En la imagen lo hemos programado en hoja de cálculo y se descubre la coincidencia de valores para n>1.


Consecuencia inmediata de esto es que L(n+1)/L(n) tiene al valor j cuando n tiende a infinito, al igual que ocurre con la sucesión de Fibonacci.

Periodicidad de la cifra de las unidades

Al igual que en otras sucesiones de Horadam. Los números de Lucas presentan un ciclo de longitud 12 en sus cifras de unidades:

 {2, 1, 3, 4, 7, 1, 8, 9, 7, 6, 3, 9}

Lo puedes comprobar en el listado: El tercer número de Lucas  es 4 y si avanzo 12 pasos en la sucesión encuentro 1364 que también termina en 4. Aunque se genera del mismo modo que la sucesión de Fibonacci, esta última no presenta este ciclo porque en ella nunca coinciden un 1 seguido de un 3.

Relaciones con los números de Fibonacci

Dos sucesiones tan similares tienen por fuerza que relacionarse de varias formas. Comenzamos con la más sencilla:

L(n) = F(n+1)+F(n-1) para n > 0.

Por inducción: Se  cumple en los primeros valores:


Si la suponemos verdadera para n,  L(n)=F(n+1)+F(n-1) se tiene: L(n+1)=L(n)+L(n-1)= F(n+1)+F(n-1)+ F(n)+F(n-2)=F(n+2)+F(n), luego se cumple y la relación queda demostrada.

L(n)=F(2n)/F(n)

Llama la atención esta igualdad, pero basta acudir a una propiedad de F(n), y es que F(2n)=(F(n+1)2-F(n-1)(Ver http://en.wikipedia.org/wiki/Fibonacci_number) y desarrollar:
F(2n)=(F(n+1)2-F(n-1)2= F(2n)=(F(n+1)+F(n-1))(F(n+1)-F(n-1))=L(n)F(n) y despejando obtenemos la relación propuesta. Por ejemplo, tomemos n=6. Tendremos: L(6)=18, F(6)=8, F(12)=144, luego F(12)=144=F(6)L(6)=18*8=144

Según estas equivalencias, cualquier fórmula expresada con números de Lucas, también se puede hacer depender de los de Fibonacci.

Una relación inversa

F(N)=(L(N-1)+L(N+1))/5

Comprobamos los términos iniciales con hoja de cálculo:


Se puede completar la demostración por inducción:

F(N+1)=F(N)+F(N-1)=(L(N-1)+L(N+1)+L(N-2)+L(N))/5 =(L(N)+L(N)+L(N+1))/5 = (L(N)+L(N+2))/5

Función generatriz

Si has leído toda la serie que llevamos publicada sobre recurrencias, no te costará trabajo entender que


Congruencias

Los números de Lucas presentan congruencias destacables:

L(p) es congruente con 1 módulo p, siendo p primo.

Puedes aprovechar para comprobarlo el listado básico que nos devuelve la hoja de cálculo recurre_lineal que venimos usando. Basta incluir la función RESIDUO aplicada a L(n) y a n y comprobarás que para índices primos el resto es 1.


Como ocurría en una situación similar con los números de Pell, la propiedad contraria no es cierta, ya que también hay números compuestos en los que el residuo es también 1. Se les da el nombre de pseudoprimos de Lucas y los tienes en https://oeis.org/A005845: 705, 2465, 2737, 3745, 4181, 5777, 672,…

L(2p) con p primo es congruente con 3 módulo p

En la imagen anterior puedes comprobar los casos de 3, 10 y 14

L(n) es par si n es múltiplo de 3 e impar en los demás casos.

Esta propiedad es casual, y debida a la definición de estos números: Los dos primeros son impares, luego el tercero, su suma, será par, el siguiente impar+par será impar y el quinto, par+impar, también será impar. Así seguiremos de forma que algunos consecutivos serán impares y el tercero par.

Existen otras congruencias más complicadas que omitimos.

Podríamos seguir, pero basta por hoy. Si encontramos más propiedades que se puedan verificar con hoja de cálculo, crearemos otra entrada.

sábado, 12 de abril de 2014

Primo mínimo detrás de un cuadrado


En la entrada anterior (http://hojaynumeros.blogspot.com.es/2014/04/comprobar-conjeturas-con-hoja-de.html) estudiamos la conjetura de Legendre y terminamos con la formulación siguiente: La conjetura de Legendre es equivalente a la afirmación de que entre dos números consecutivos n y n+1 siempre existe un número que es la raíz cuadrada de un número primo.


La conjetura nos afirma que existe uno al menos, pero lo normal es que existan más. Nos fijaremos en el primer número primo que es mayor que un cuadrado dado n2, y que, por tanto, su raíz cuadrada sea la más cercana de este tipo al valor de n. Esos valores son fáciles de encontrar. Aquí tienes una función en BASIC:

Function primomincuad(n)
 a=n*n+1
while not esprimo(a)
a=a+1
wend
primomincuad=a
End function

Dado un valor de n, esa función encuentra el menor número primo que es mayor que su cuadrado. Ya se conocen los valores de estos primos:

2, 5, 11, 17, 29, 37, 53, 67, 83, 101, 127, 149, 173, 197, 227, 257, 293, 331, 367, 401, 443, 487, 541, 577, 631, 677, 733, 787, 853, 907, 967, 1031, 1091, 1163…
http://oeis.org/A007491

Las raíces cuadradas de estos números estarán comprendidas entre n y n+1. Por ejemplo, el octavo, que es 67, tiene su raíz cuadrada entre 8 y 9, como se ve sin calcularla.

Estos valores nos plantean una pregunta inocente: ¿Qué diferencias concretas existen entre cada número natural y la raíz cuadrada de primo más próxima?

Para encontrar esa raíz podemos usar la fórmula a = RAIZ(PRIMPROX(N ^ 2)). La hemos utilizado para crear este gráfico de diferencias:



Es muy curioso, porque esas diferencias oscilan con tendencia decreciente desde 0,4142 hasta acercarse a cero. Podíamos plantearlo como una conjetura:

Conjetura 1: Las diferencia entre cualquier número natural y la raíz cuadrada del mínimo número primo mayor que su cuadrado es siempre igual o menor que la raíz cuadrada de 2 menos 1.

Es razonable pensar en esta conjetura. Por una parte la hemos comprobado hasta 5*10^7 con este código PARI:

{for(i=1,5*10^7,b=sqrt(nextprime(i*i))-i;c=sqrt(2)-1;if(b>=c,print(i)))}

Si lo ejecutas verás que sólo imprime el valor 1. Los siguientes números producen diferencias más pequeñas.

Por otra, vemos que los valores son claramente decrecientes en conjunto. Realizamos algunas aproximaciones. ¿Cuántos primos se pueden esperar entre n2 y  (n+1)2?

Si usamos el Teorema de los números primos podemos establecer una aproximación grosera

(http://es.wikipedia.org/wiki/Teorema_del_n%C3%BAmero_primo)


Y más grosera y atrevida aún: si se esperan P primos entre los dos cuadrados consecutivos, el primero de ellos distará de n2 una distancia del orden de la fracción inversa, 2Ln(n)/(2n+1). ¿Será así? Recuerda que hablamos de tendencias, no de valores individuales.

Hemos construido una tabla doble: en una columna los valores de RAIZ(PRIMPROX(N ^ 2))-N y en la otra los de 2Ln(n)/(2n+1), con este resultado gráfico:









Vemos que la tendencia decreciente es razonable, luego podemos confiar en que nuestra conjetura sea cierta, que las diferencias nunca son mayores que 0,4142…¡Sólo confiar, nada más!

Conjetura 2: Dado un número natural cualquiera K, existe otro N tal que la diferencia (en valor absoluto) entre su cuadrado N2 y el mínimo primo mayor que él sea igual a K.

Expresado de otra forma, la expresión PRIMPROX(N ^ 2)-N^2 puede tomar cualquier valor.  Esta idea aparece cuando obtienes una lista de valores de N, tomas nota de esa diferencia en una hoja de cálculo y la ordenas después por los valores de la diferencia. No nos cabe aquí la tabla adecuada para que veas que se recorren todos los valores, pero puedes construirla en la hoja de cálculo conjeturas,xlsx  (ver http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#conjeturas)

Algunos valores se resisten a salir, como el 29, 68 y 78, pero al final los obtienes. Puedes construir esta función que te devuelve el primer valor posible para K:

Public Function difproxprim(k)
Dim n, m
n = 0: m = -1
While k <> m
n = n + 1
m = primprox(n * n) - n * n
Wend
difproxprim = n
End Function

Si juegas con ella te darás cuenta de que puede resultar muy lenta en una hoja de cálculo, por ejemplo para obtener que el 68 aparece en la lista para K=5187.

Puedes usar la misma idea en PARI:

difproxprim(k)={local(m=-1,n=0);while(k<>m,n=n+1;m=nextprime(n*n)-n*n);return(n)}
{print(difproxprim(68))}

En ella sustituyes después el 68 por otro número. Por ejemplo, el 88 se retrasa hasta K=11499 y el 200 hasta K=90963. Es un poco atrevido plantear esta conjetura, pero también es razonable.

jueves, 3 de abril de 2014

Comprobar conjeturas con hoja de cálculo – Legendre


Conjetura de Legendre

Esta conjetura afirma que entre dos cuadrados consecutivos n2 y (n+1) 2 existe siempre un número primo.

Se considera básica e importante, por lo que se incluyó en los Problemas de
Landau (http://en.wikipedia.org/wiki/Landau%27s_problems)

Al igual que en la conjetura de Andrica (http://hojaynumeros.blogspot.com.es/2014/03/comprobar-conjeturas-con-hoja-de.html) sólo necesitamos para estudiarla las funciones ESPRIMO y PRIMPROX, incluidas en la herramienta que hemos preparado para el estudio de conjeturas.

 (ver http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#conjeturas)

Es fácil organizar los cálculos. Diseñamos una columna con los primeros números naturales y junto a ella la de sus cuadrados. Después, a la derecha de cada cuadrado calculamos la función PRIMPROX sobre él para encontrar su próximo primo. Este deberá pertenecer al intervalo formado por ese cuadrado y el siguiente:

A simple vista vemos que cada primo de la tercera columna es menor que el siguiente cuadrado: 67 menor que 81, luego está comprendido entre 64 y 81, o 149, que pertenece al intervalo (144, 169), y así con todos.

Nada impide que comiences la lista no con el 1, sino con un cuadrado mayor, como ves en la imagen



Si lo vas a explicar a otras personas, podías añadir una cuarta columna con una fórmula de tipo condicional =SI(el primo es menor que el siguiente cuadrado;”Vale”;”Error”)

De hecho, no existe sólo un número primo entre dos cuadrados, sino que pueden entrar más. Tienes ese dato en http://oeis.org/A014085. Puedes descubrirlo tú con la función PRIMPROX. Sólo copiamos un esquema para el cuadrado de 26, con un resultado de 7 primos:



Si construyes bien un esquema similar podrás encontrar el número de primos entre otros cuadrados consecutivos.

Otro ejercicio sencillo sería, dado un número primo encontrar entre qué cuadrados está. No necesitas saber mucho ¿Cómo se haría? Recuerda la función ENTERO. Ahí tienes un ejemplo:



Otra formulación

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í:


En nuestra herramienta conjeturas.xlsm hemos implementado la función PPI(n) (le añadimos una p para que no se confunda con el número p, que se expresa como PI()) Con ella es fácil verificar la conjetura: escribes los dos cuadrados consecutivos y le aplicas la función PPI a cada uno. Restas y deberá darte un número mayor que 0. Puedes construirte un esquema de cálculo similar al de la imagen:



En la página http://oeis.org/A014085 citada más arriba se incluye una generalización de esta conjetura, en el sentido de el exponente 2 se podría sustituir por otro más pequeño. Se ha conjeturado que se podría llegar hasta log(127)/log(16)= 1,74717117169. Se entiende que con carácter general, para todos los valores. Más abajo verás que en un caso particular se puede llegar a valores más pequeños.

Si el esquema anterior lo modificamos para que en lugar de un cuadrado usemos el exponente que deseemos nos servirá para acercarnos al valor mínimo en el que la conjetura sigue siendo cierta:



Nos hemos dedicado a aproximar este caso al valor mínimo posible y hemos llegado hasta el exponente 1,20545 como mero entretenimiento.

Andrica y Legendre

Si la conjetura de Andrica es cierta (ver http://hojaynumeros.blogspot.com.es/2014/03/comprobar-conjeturas-con-hoja-de.html), de ella se deduce la de Legendre. En efecto, vimos en la entrada enlazada que la diferencia entre un primo Pn y el siguiente Pn+1, si la conjetura de Andrica se verdadera, debería cumplir la desigualdad

De ella se deduciría la de Legendre fácilmente. Supongamos que alguien descubre que entre dos cuadrados consecutivos n2 y (n+1)2 no existe ningún número primo. En este caso llamemos pn al primo inmediatamente menor que n2. Sería pn<n2<pn+1. Según la desigualdad anterior ocurriría que si no existiera ningún primo entre n2 y (n+1)2 tendríamos


Esto está en contradicción con la desigualdad previa, luego ha de existir un primo entre ambos cuadrados.

Otra formulación más

Es evidente que la conjetura de Legendre es equivalente a la afirmación de que entre dos números consecutivos n y n+1 siempre existe un número que es la raíz cuadrada de un número primo. Pero esto nos va a dar juego para otra entrada.