Restos cuadráticos - Criterio de Euler

En la entrada anterior iniciamos el estudio de los restos cuadráticos respecto a un módulo. Descubrimos un procedimiento algo lento para encontrar los restos y los no restos. En esta otra entrada simplificaremos algo el proceso y aprenderemos nuevos conceptos. Se aconseja leer previamente dicha entrada.

El recorrer todos los restos desde 1 hasta (p-1)/2 puede hacerse muy pesado en el caso de valores muy grandes. Euler descubrió un criterio que nos ayuda a distinguir los restos de los no restos con un solo cálculo. Es este:

Si a es un resto cuadrático respecto a p (primo e impar) se cumple

Y si no lo es

Es una consecuencia del Teorema de Fermat:

Luego, como p-1 es par, podemos escribir

De esta congruencia deducimos que uno de los paréntesis es congruente con cero, pero ambos no pueden serlo, porque entonces su diferencia, 2, cumpliría 2º0 y eso es imposible para p primo impar.

De hecho, si a es resto cuadrático, el que se cumple es el segundo, ya que si existe un x tal que x²ºa (mod p) entonces a^(p-1)/2ºx^p-1º1 (mod p) de nuevo por el Teorema de Fermat.

Como sólo se puede cumplir una congruencia, si a  es no resto cuadrático, cumplirá la otra, con el -1.

Este criterio es bastante directo, para saber si un valor es resto cuadrático. Por ejemplo, ¿Es el 14 resto cuadrático respecto al 23?

14^(23-1)/2=14¹¹ Calculamos el resto de este último por potencias sucesivas: 14¹º14 (mod 23), 14²º12 (mod 23) 14⁴º12*12º6 (mod 23) 14⁸º6*6º13 (mod 23), luego 14¹¹º13*12*14º-1 (mod 23), luego no es resto cuadrático.

La herramienta de hoja de cálculo que proponemos, en su tercera hoja, te realiza los cálculos la aplicación de este criterio:

Es conveniente que lo intentes sin hoja de cálculo para practicar. Puedes usar la exponenciación modular (http://hojaynumeros.blogspot.com.es/2012/03/de-la-multiplicacion-rusa-la.html). La usaremos en el siguiente ejemplo:

¿Es resto cuadrático el número 70 respecto al módulo 101?

El módulo 101 es primo e impar, luego podemos usar el criterio de Euler. Bastará elevar 70 a (101-1)/2=50.

Sabemos que 50=32+16+2, luego vamos calculando: 70¹º-31 (mod 101), : 70²º31*31º-49 (mod 101), 70⁴º49*49º-23 (mod 101), 70⁸º23*23º24 (mod 101), 70¹⁶º24*24º-30 (mod 101), 70³²º30*30º-9 (mod 101), y ahora construimos el 50:

70⁵⁰º70³²70¹⁶70²º-9*30*49º1 (mod 101), luego según el criterio, 70 sí es resto cuadrático. Si lo compruebas con la herramienta que proponemos descubrirás que su raíz cuadrada es 26.

La aplicación de este criterio nos lleva a propiedades muy interesantes.

La primera es tan elemental que no tenemos que justificarla:

El producto de dos restos o de dos no-restos siempre da un resto, y el de resto con no resto produce un no-resto. Es decir, poseen estructura alternada, por lo que es fácil representar los restos mediante el signo + y los no restos con el -, y así poder usar la regla de los signos. Se razona fácilmente a partir del criterio de Euler.

Consecuencia inmediata:

El conjunto de restos cuadráticos forma un grupo multiplicativo en Zp

Por ejemplo, si m=11, los restos son 1, 3, 4, 5 y 9 y los no restos 2, 6,7, 8 y 10 (o bien -1, -3, -4, -5 y -9). Los restos forman un grupo, como se puede verificar fácilmente.

En la segunda hoja de la herramienta que ofrecemos dispones de una calculadora para comprobar las afirmaciones anteriores.

En particular puedes estudiar que si llamamos C al grupo de los restos cuadráticos, las clases laterales tipo a*C tienen cardinal (p-1)/2 y que por tanto el índice de C respecto a Zp es 2. Vemos una de esas clases. Multiplica el elemento 6 de Z11, por todos los elementos de C, en este caso 1, 3, 4, 5, 9: 6*1º6 (mod 11), 6*3º7 (mod 11), 6*4º2 (mod 11), 6*5º8 (mod 11), 6*9º10 (mod 11). Han resultado valores distintos, luego el cardinal de 6*C es (11-1)/2=5

Símbolo de Legendre

Esta estructura como grupo multiplicativo se expresa muy bien mediante el símbolo de Legendre (por comodidad tipográfica lo escribiremos como (m/p), con los dos números en línea, como hace Apostol).

Llamamos Símbolo de Legendre a una función que asigna a cada par de valores m y p, este último primo e impar, los siguientes valores:

(m/p)=1 si m es resto cuadrático respecto a p
(m/p)=-1 si m es no-resto cuadrático respecto a p
(m/p)=0 en el caso particular en el que m sea múltiplo de p.

En realidad, si recordamos el criterio de Euler, podemos usar una fórmula directa para encontrar el valor de un símbolo de Legendre:

Según lo explicado anteriormente, es fácil ver que esta función es multiplicativa:

Esto tiene una consecuencia práctica, y es que se pueden eliminar cuadrados al calcular el símbolo de un número compuesto.

Nótese que el valor del símbolo de Legendre es una propiedad de las clases de restos y no de los números concretos, por lo que es fácil entender que si aºb (mod p). entonces (a/p)=(b(p)

Restos cuadráticos

En esta entrada y otras posteriores trataremos el tema de las congruencias de segundo grado. Usaremos como siempre las hojas de cálculo, y, en especial una herramienta que hemos creado para este fin. Todo el tema gira alrededor de la ecuación

 

Imagina una clase de restos, por ejemplo la correspondiente a módulo 7, {0, 1, 2, 3, 4, 5, 6} Elige un resto, sea el 5. ¿Existirá otro resto que multiplicado por sí mismo dé como resultado 5, módulo 7? Probemos: 1*1º1, 2*2º4, 3*3º2, 4*4º2, 5*5º4, 6*6º1. Así que no es posible, los únicos resultados  son 1, 4 y 2. Nunca resulta un 5, ni tampoco 3 ni 6.

Podemos resumir esta situación calificando 1, 2 y 4 como “restos cuadráticos” y 3, 5 y 6 como “no restos cuadráticos”. También podemos hablar de la “raíz cuadrada” de los primeros: 1²=1, 3²=2 y 2²=4. Es fácil ver que si k es raíz de n, también lo es m-k. Eleva esta última al cuadrado y lo comprobarás.

Esta situación la tendrás siempre. Unos elementos podrán ser restos cuadráticos y otros no. El primer intento que hemos hecho para averiguarlo ha sido el probar los elementos uno a uno hasta conseguir que el cuadrado de uno de ellos coincida con el resto dado, o bien comprobar que esto es imposible y que se trata de un “no resto cuadrado”.

Para estudiar el tema con profundidad puedes acudir a

http://hojamat.es/parra/restocuad.pdf
http://mate.dm.uba.ar/~pdenapo/teoria_analitica_de_numeros/clase11.pdf
http://en.wikipedia.org/wiki/Quadratic_residue

Diremos que a es resto cuadrático módulo p, coprimo con él, cuando exista una solución a la ecuación



Con hoja de cálculo (o con ligeras variaciones, en cualquier lenguaje de programación) podemos automatizar este procedimiento. Definiremos una función, que dependa de un resto dado y del módulo correspondiente, que nos devuelva la raíz cuadrada, con lo que sabremos que es resto cuadrático, o bien un cero si no lo es.

Public Function restocuad(n,modu) ‘los parámetros son el resto y el módulo
Dim k, r,s
Dim es As Boolean

es = False ‘ nos indica que aún no se ha encontrado una raíz
k = 1 ‘contador que busca la raíz
r = 0 ‘raíz encontrada
While k <= modu / 2 And Not es ‘va buscando las posibles raíces
s=(n-k*k)/modu
If s=int(s) Then es = True: r = k ‘se ha encontrado la raíz
k = k + 1 ’seguimos buscando
Wend
If es Then restocuad = r Else restocuad = 0 ‘devuelve un cero si no se ha encontrado
End Function

Con esta función implementada, puedes analizar qué restos son cuadráticos, formar tablas de restos y no restos y resolver la ecuación x²ºa, o, con los cambios adecuados, la ecuación general de segundo grado. Lo vemos con un ejemplo:

Resolver x²-26x+10º7 (mod 11)

Damos estos pasos:

x²-26x+10 º (x-13)²-159 º 7 (mod 11)
(x-13)²º166 (mod 11)
(x-13)²º1 (mod 11)

Buscamos la raíz cuadrada de 1 y resulta ser 1 o -1 (o 10) es decir:

(x-13)º1 o 10 (mod 11)

Despejando: x=3 y x=1

Comprobamos: 3²-26*3+10=-59 º-4 º 7 (mod 11) y 1²-26*1+10=-15 º-4 ?º7 (mod 11)

Hemos elegido un ejemplo que tenía solución, pero si llega a aparecer un no resto en lugar de 1, no podríamos seguir. Por eso es tan importante saber previamente si un resto es cuadrático o no.

Caso de módulo primo e impar

En este caso, si consultas la teoría descubrirás que si p es el módulo primo e impar resulta que el número de restos cuadráticos es (p-1)/2, que son congruentes con 1², 2², 3²,…,((p-1)/2)² y por tanto, este también es el número de no-restos.

Previamente estudia esta propiedad:

La ecuación x²º a (mod p) para un a dado, o no tiene solución, o tiene dos.

En efecto, si tiene una solución x1 con x1²º a (mod p)  también será solución –x1 y sólo tenemos que demostrar que ambas son distintas. Es fácil: si fueran iguales tendríamos que 2x1=0, pero ni 2 ni x1 son divisores del cero, por ser p primo impar. La segunda solución la puedes expresar como p-x1

Por tanto, el número de restos cuadráticos no sobrepasará (p-1)/2. Es más, es igual que ese número, porque los restos de 1², 2², 3²,…,((p-1)/2)² no se repiten , ya que una igualdad entre ellos haría que la ecuación  x²º a (mod p) tuviera cuatro soluciones en lugar de dos.

Esta propiedad te ofrece un procedimiento para encontrar todos los restos cuadráticos en este caso, y es calcular los valores de  1², 2², 3²,…,((p-1)/2)² y los resultados serán los restos cuadráticos, y los demás será no restos.

Hemos preparado una herramienta en  hoja de cálculo

 (ver http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restoscuad),

cuya primera prestación es la de encontrar el conjunto de restos y no restos para un módulo primo e impar. En ella está implementado el procedimiento de ir calculando los valores de .1², 2², 3²,…,((p-1)/2)²  La novedad de este esquema es que va situando los restos en una columna y los no restos en otra.

En la imagen figuran los 15 restos módulo 31, sus raíces, y los 15 no restos. Para ver cómo lo logra tendrías que acceder al Basic, pero no lo analizaremos en este momento.

Su funcionamiento en esta parte es muy simple: escribes el nuevo módulo,  y después pulsas el botón de Restos y no restos  para que aparezcan.

Puedes alternar tus cálculos manuales con los de la hoja para entenderlo todo mejor y comprobar resultados.

En la siguiente entrada simplificaremos los cálculos necesarios para saber si un resto es cuadrático o no mediante un criterio debido a Euler.

Distancia de Hamming entre números de igual tipo

(Con esta entrada despedimos el curso 2013-14. En septiembre volovemos)

Hamming definió su distancia para palabra binarias como el número total de bit en los que ambas se diferencian, comparando, como es de esperar cada uno con el que ocupa el mismo lugar en la otra palabra. Así, la distancia de Hamming entre 11001011 y 11100011 es de 2, porque son diferentes entre sí los dígitos resaltados en negrita.

Es fácil extender esta definición a cadenas de caracteres o a las cifras de un número. Así, la distancia entre estos números de móvil 656232110 y 636182170 es de 4, que son las cifras en las que difieren. Con esta definición nos podíamos preguntar cómo se relacionan entre sí números del mismo tipo: primos con primos o cuadrados con cuadrados. La idea viene a cuento porque esperamos que en los primos abunden las cifras impares, o que en los cuadrados aparezcan 1, 4, 9, 6 o 5, o que en los triangulares o de Fibonacci se distribuyan uniformemente. Como siempre advertimos, hay que decir que esto sólo es una curiosidad sin valor matemático.

Para ello hemos construido la función hamming(a,b) (para el Basic de las hojas de cálculo), que cuenta las cifras diferentes existentes entre dos números. Hemos previsto el valor -1 como valor de error. Para aquellos que no tengan el mismo número de cifras, las de uno que no están en el otro se cuentan como diferencias. Su listado es el siguiente, aunque no lo explicaremos, ya que contiene varias funciones predefinidas:

Public Function hamming(a, b) 'devuelve -1 si algo va mal. Cuenta las diferencias entre cifras. Si uno es más largo que el otro cuenta los huecos también

Dim h, i, n, m

h = -1
If esentero(a) And esentero(b) Then
n = numcifras(a)
m = numcifras(b)
h = 0
If n > m Then h = n - m: n = m
For i = 1 To m
If cifra(a, i) <> cifra(b, i) Then h = h + 1
Next i
End If
hamming = h
End Function

Con esta función analizaremos qué números presentan más o menos diferencias con sus compañeros de tipo. Para no complicar la tarea, que al fin y al cabo es lúdica, nos limitaremos a comparar aquellos que tengan el mismo número de cifras. Comenzamos:

Distancias entre primos

Comenzamos con los de dos cifras. El valor de la función sólo podrá ser 1 o 2, porque el 0 indicaría igualdad. Comparamos cada primo de dos cifras con todos los demás, tomando nota de la distancia existente entre ellos. Nos ha resultado esta tabla:

En ella hemos reflejado las distancias de cada uno de los 21 primos de 2 cifras respecto a sus compañeros. En la segunda columna contamos las distancias de Hamming que valen 1 y en la siguiente las de 2. En la última columna se ha calculado la media ponderada de las distancias. Viendo las columnas se destaca que son mucho más abundantes las diferencias h=2.

Es fácil ver que el 97 es el primo que más diferencias presenta, el que está más alejado en cifras de los demás. En total 36 diferencias (4+2*16). Por el contrario, para el 13 hay 32, (8+2*12). Para comparar este colectivo con otros, hemos sumado todas las diferencias, con un resultado de 716 y una media de 34,095.

Primos de tres cifras

Como aquí aparecerán más resultados, usaremos un filtro para presentarlos. Los primeros valores de los 143 totales son:

Mediante ordenaciones y filtros en la hoja de cálculo descubrimos lo siguiente:

El primo más cercano a sus compañeros es el 157. Ha sido una sorpresa, pues no pensamos en él. Es curioso que los seis siguientes en la lista terminen en 7. Estos son los que tienen las cifras menos destacadas.

En el extremo opuesto, de los que presentan más diferencias han resultado números terminados en 9. A ver quién aclara esto (¿pura casualidad o hay algo detrás?)

Hay un triple empate entre 719, 919 y 929. Los tres se encuentran a una distancia media de los demás igual a 61,5, o una suma de diferencias de 369.

La suma de todas las diferencias es 51842, con un promedio de 362,5

Primos de cuatro cifras

Los más afines en cifras son

Y los más alejados

Con esta idea nos quedamos. El total de diferencias es de 3870022 con una media de 3647,5

Resumiendo, el resultado global es

En la última columna dividimos de nuevo ente los elementos, ya que su número influye en las distancias medias (hay más con los que comparar)

Estas medidas nos servirán para comparar la homogeneidad de las cifras ordenadas respecto a otros colectivos. Veremos ahora los cuadrados, triangulares y cualquier otro colectivo que nos llame la atención.

Distancias entre cuadrados

Los cuadrados son menos abundantes. En concreto, para dos cifras solo existen 6. Llama la atención en la tabla resumen que sólo un par (16 y 36) presenta una distancia de 1, mientras el resto se diferencia totalmente de los demás.

Las diferencias son muy uniformes. Los más afines son los ya destacados 16 y 36

Cuadrados de tres cifras

Aparecen 22 cuadrados. Los que tienen cifras más parecidas a sus compañeros son estos:

También es una sorpresa que el 121 comparta más dígitos que ningún otro. La clave está en los 13 con los que se diferencia en dos cifras.

Los que más se alejan:

Se ve que el 6 no es una terminación tan popular como creíamos.

Con cuatro cifras

Resultan 68 cuadrados. Los ordenamos como en los casos anteriores. Vemos los que presentan menos diferencias con los demás tienen todos una cifra 0

También es sorprendente que el mínimo caiga precisamente en 1024, el elemento más pequeño del conjunto.

Los que más se alejan terminan todos en 6. Otra casualidad.

Resumen

Distancias entre triangulares

Sólo damos los resultados más llamativos

Triangulares más afines: De dos cifras, el 15, de tres el 120 y de cuatro hay dos, el 1275 y el 1770
Triangulares más diferentes: Hay cinco de dos cifras: 10, 36, 66, 78 y 91. De tres cifras 378 y 528. De cuatro el 6903

No seguimos. No parece que el tipo de número influya mucho en los resultados si corregimos los totales según el número de elementos. Puede más la falsa aleatoriedad que produce la repetición que las diferencias del tipo de cifras.

Suma de dos números primos consecutivos (2)

En la anterior entrada vimos algunos hechos que ocurren al sumar dos números primos consecutivos. Hoy terminamos con un catálogo de resultados que puede presentar esa suma.

La suma es cuadrado

En http://oeis.org/A061275 se recogen los casos en los que la suma de dos primos consecutivos da un cuadrado:

17, 47, 71, 283, 881, 1151, 1913, 2591,… (primer primo del par)

Por ejemplo, 17+19=36=6². Igualmente 47+53=100=10², 71+73=144=12²

El cuadrado será par, y por tanto un múltiplo de 4. Si un elemento del par de primos es del tipo 4n+1, el otro deberá ser de la clase 4n+3, para que no resulte un múltiplo de 2 que no lo sea de 4, y así impida que resulte un cuadrado. Como los primeros se pueden descomponer en sumas de cuadrados, un elemento del par tendrá siempre la forma A²-B²-C². Por ejemplo, en el par (103049, 103067), 103067=454²-157²-280².

Suma triangular

Están contenidos en https://oeis.org/A225077:

17, 37, 59, 103, 137, 149, 313, 467, 491, 883, 911, 1277, 1423, 1619, 1783, 2137, 2473, 2729, 4127, 4933, 5437, 5507, 6043, 6359, 10039, 10453, 11717,…

Así, el par de primos gemelos (2087,2089) tiene como suma 41616=288*289/2, que es el triangular número 288.

Suma doble de un cuadrado

Este caso es interesante porque en ellos la media aritmética de los dos primos consecutivos sería un cuadrado. Así ocurre con 1087 y 1091, cuyo promedio es 1089, el cuadrado de 33.
En ese caso un primo es n²-k y el otro n²+k. Si k=1 tendríamos un par de primos gemelos. Sólo hemos encontrado el par (3,5), cuya media es el cuadrado de 2. No puede haber más, porque para que n²-1 sea primo, ha de ser n-1=1 y eso sólo ocurre en n=2 y el par (3,5).

Los términos de esta sucesión son

 3, 7, 61, 79, 139, 223, 317, 439, 619, 1087, 1669, 2593, 3593, 4093, 5179, 6079, 8461, 12541, 13687, 16633, 19037, 19597, 25261, 27211, 28219, 29581, 36857, 38011, 39199, 45361, 46649, 47521, 51977, 56167… https://oeis.org/A225195

Forman una subsucesión de http://oeis.org/A053001, que contiene los números primos mayores que son anteriores a un cuadrado. Los que estudiamos aquí cumplen esa condición, porque al ser el cuadrado la media entre dos primos consecutivos, el menor de ellos tendrá la propiedad pedida en A053001.

Otros casos

La suma puede ser una potencia perfecta:

3, 17, 47, 61, 71, 107, 283, 881, 1151, 1913, 2591, 3527, 4049, 4093, 6047, 7193, 7433…

https://oeis.org/A091624

Como casos particulares están publicados los cuadrados (http://oeis.org/A061275) y los cubos(https://oeis.org/A061308)

O el doble de una potencia perfecta:

3, 7, 61, 79, 139, 223, 317, 439, 619, 1087, 1669, 1723, 2593, 3593, 4093, 5179, 6079, 8461, 12541, 13687, 16633, 17573, 19037, 19597,…

En este caso la media de los dos primos será una potencia perfecta, y ambos se pueden representar por k^m-h y k^m+h, con k y h coprimos y no siendo h una potencia de exponente m (¿por qué?)

No es difícil encontrarlos. Con esta línea de PARI lo consigues.

{forprime(i=3,10^6,k=(i+nextprime(i+1))/2;if(ispower(k),print(i,", ")))}

(La hemos publicado en https://oeis.org/A242380)

Un caso particular interesante es cuando la media es un cubo. Los primos consecutivos serían del tipo k³-h y k³+h, con k y h coprimos y no siendo h un cubo. De esto también se deduce que un elemento de la sucesión es el mayor primo anterior a un cubo, y que por tanto pertenece también a la secuencia http://oeis.org/A077037

Son estos:

61, 1723, 4093, 17573, 21943, 46649, 110587, 195103, 287491, 314423, 405221, 474547, 1061189, 1191013, 1404919, 1601609, 1906621, 2000371, 2146687, 2196979, 3241783, 3511799, 4912991, 5268017, 6229501, 6751267, 6858997, 7077883, 11239421, 20346407, 21951997, 26198063,…

Los puedes reproducir con PARI

{for(i=3,3*10^7,if(isprime(i),k=(i+nextprime(i+1))/2;if(ispower(k,3),print(i,", "))))}

(publicados desde este blog en https://oeis.org/A242382)

En realidad se pueden probar otros casos por puro entretenimiento, y después incorporarlos a OEIS para que queden en esa extensa base de datos. Pueden ser estos:

Media oblonga

Se conocen ya los primos consecutivos cuya suma es un número oblongo (del tipo n(n+1) o bien doble de un triangular). Están contenidos en http://oeis.org/A154634. Los que aportamos desde este blog son aquellos cuya media es oblonga:

5, 11, 29, 41, 53, 71, 239, 337, 419, 461, 503, 547, 599, 647, 863, 1051, 1187, 1481, 1721, 1801, 2549, 2647, 2969, 3539, 4421, 6317, 7129, 8009, 10301, 12653, 13567, 14033, 17291, 18353, 19181, 19457, 20021, 22943, 23561, 24179, 27059, 29063, 29753, 31151, 33301…
(https://oeis.org/A242383)

Una propiedad curiosa es que están contenidos en http://oeis.org/A161550. La razón es que si un número primo pertenece a la sucesión que presentamos, en la que su media con el próximo primo es un oblongo del tipo n(n+1)=n²+n, es claro que será el máximo primo inferior a n²+n, que es la definición de A161550. Por el contrario, un término de esta sucesión no tiene que cumplir nuestra condición. Así, el 19 es el máximo primo inferior a 4²+4=20, pero su media con el siguiente primo no es 20: (19+23)/2=21.

Los puedes encontrar con PARI:

{for(i=3,10^5,if(isprime(i),k=(i+nextprime(i+1))/4;if(issquare(8*k+1),print1(i,", "))))}

En el código se buscan pares de primos cuya suma dividida entre 4 produzca un triangular. Es otra forma de definirlos.

Suma del tipo n(n+2)

Estos números del tipo n(n+2) se pueden expresar también como (n+1)²-1. Salvo el caso n=1 ninguno puede ser primo. No es muy frecuente el que dos primos consecutivos produzcan este tipo de número. Los primeros son estos:

3, 11, 59, 139, 179, 311, 419, 541, 919, 1399, 1621, 2111, 3119, 5099, 6379, 8059, 8839, 9377, 15661, 16007, 16741, 17107, 21011, 21839, 23539, 24419, 28081, 30011, 31489, 33533, 35617, 37811, 39461, 41759, 44699, 45293, 60899, 68819, 71059, 78007, 83639, 84457, 86111, 87767, 92867, 99901,…(https://oeis.org/A242384)

Según el párrafo anterior se pueden ir sumando los pares de números primos consecutivos, sean p y q, y exigir que p+q+1 sea un cuadrado. Así los hemos encontrado con hoja de cálculo y con PARI:

{k=2;while(k<10^5,l=nextprime(k+1);if(issquare(k+l+1),print1(k,", "));k=l)}

Si efectuamos las sumas entre los pares de números consecutivos encontrados, es evidente que n(n+2) será par, luego n también lo será. Si elegimos un número primo de la sucesión, por ejemplo el 2111, su próximo primo será 2113, y su suma 4224 es igual a 64(64+2), con n=64, par.

Media del tipo n(n+2)

Es un caso similar al anterior, pero con cambios importantes. Los primeros primos que cumplen esto son:

13, 97, 113, 193, 283, 397, 479, 673, 953, 1439, 1597, 2297, 2699, 3469, 4219, 4483, 5323, 7219, 8273, 9209, 9403, 10799, 12097, 13219, 14879, 15373, 15619, 21313, 23399, 26237, 27883, 32029, 32749, 34217, 37243, 39989, 41203, 42433, 43669, 46219, 55219, 60509, 62497, 72353, 75619, 93001,…(https://oeis.org/A242385)

El código para encontrarlos es

PARI: {k=2;while(k<10^5,l=nextprime(k+1);if(issquare((k+l)/2+1),print1(k,", "));k=l)}

En ellos la media de los dos consecutivos incrementada en una unidad se convierte en un cuadrado. Por ejemplo, el primo consecutivo a 9209 es 9221. Su media 9215 y si le sumamos una unidad resulta 9216=96²

Por último, capicúas

Terminamos con dos ejemplos más. El primero recoge los pares de primos cuya suma es capicúa (incluidos los de una cifra):


2, 3, 109, 211, 347, 409, 1051, 1493, 2111, 2273, 3167, 4219, 4441, 10099, 10853, 10903, 11353, 11909, 12823, 12973, 13421, 13831, 14543, 14639, 20551, 21011, 21347, 21661, 21863, 22271, 23581, 23981, 30047, 30557, 31259, 31307, 31963, 32069, 32213, 32467, 32869, …

Encontrarlos con PARI es algo más complicado: la función palind devuelve VERDADERO si el número es igual a su simétrico en cifras. El resto es fácil de entender:


palind(n)=Str(n)==concat(Vecrev(Str(n)))
{p=2;while(k<10^5,q=nextprime(p+q);if(palind(p+q),print1(p,", "));p=q)}

Los tienes en (https://oeis.org/A242386)


Con media capicúa

Con una codificación similar se pueden encontrar aquellos primos consecutivos cuya media es capicúa:

3, 5, 7. 97, 109, 281, 359, 389, 409, 509, 631, 653, 691, 743, 827, 857, 907, 937, 967, 1549, 2111, 2767, 4219, 4441, 7001, 9007, 9337, 9661, 10099, 11503, 12919, 13421, 16759, 17569, 21011, 21611, 23831, 26261, 26861, 28181, 29287, 29483, 30497, 31307, 32213, 33029, 33629

palind(n)=Str(n)==concat(Vecrev(Str(n)))
{k=2;while(k<10^5,l=nextprime(k+1);if(palind(k+l),print1(k,", "));k=l)}

(https://oeis.org/A242387)

Suma de dos números primos consecutivos (1)

¿Qué ocurre si sumamos dos primos consecutivos mayores que 2?

En primer lugar, nunca resulta un semiprimo: ambos son impares, luego la suma tendrá el factor 2. Por otra parte, la suma es el doble de su media aritmética, que por estar entre ellos no será un número primo, luego aportará a la suma al menos dos factores primos más, por lo que nunca será semiprimo.

Según sean ambos primos del tipo 4k+1 o 4k+3, se puede obtener un múltiplo de 4 o uno de 2 que no sea de 4. Es curioso ver que si la diferencia entre ellos no es múltiplo de 4, la suma sí lo es. Al contrario, si la diferencia entre ellos es divisible entre 4, la suma no lo será. Intenta razonarlo, que no es difícil. Por ejemplo, 7+11=18, que no es múltiplo de 4, mientras que 11-7 sí lo es. Por contra, 17 y 19 se diferencian en 2 y su suma 36 es múltiplo de 4.

Sucesión de sumas

Al contrario ¿Qué números pares son suma de números primos consecutivos? Tienes el resultado, con el añadido del 5, en http://oeis.org/A001043

5, 8, 12, 18, 24, 30, 36, 42, 52, 60, 68, 78, 84, 90, 100, 112, 120, 128, 138, 144, 152, 162, 172, 186, 198, 204, 210, 216, 222, 240, 258, 268, 276, 288, 300, 308…

(En todas las sucesiones de esta entrada incluieremos sólo el primo más pequeño del par. El otro lo puedes encontrar con las funciones PRIMPROX o NEXTPRIME).

Prescindiendo del 5, caso aislado, podemos encontrar algunas características interesantes:

Su gráfica está muy bien aproximada por defecto mediante 2nln(n). Esto ocurre porque nln(n) es cota inferior cercana de la función prime(n), y al sumar primos consecutivos se aproxima como si fuera el doble.

Si prescindimos del 5, todos serán pares y tendrán un Mayor divisor impar (MDI) que siempre será propio. El gráfico de los MDI es este

La primera rama se corresponde con los MDI cuando el 2 está elevado a la unidad, la segunda para los múltiplos de 4 y así hasta abajo.

Estaba inédita la sucesión de las valuaciones de esas sumas respecto a 2:

3, 2, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 4, 3, 7, 1, 4, 3,… y la hemos publicado en https://oeis.org/A237881 con la inclusión del caso 2+3

Charles R Greathouse IV  ha añadido las acotaciones a(n) << log n; en particular, a(n) <= log_2 n + log_2 log n + O(1).

En PARI se podría buscar así:

{for(i=1,200,k=valuation(prime(i)+prime(i+1),2);print1(k,", "))}

Observando la gráfica de más arriba nos podemos preguntar con qué frecuencia aparecen los valores 1, 2, 3,… en la sucesión, para un rango determinado.

Para valores naturales, los números con valuación 0 tendrán frecuencia doble que los de valuación 1, y estos el doble que los de valuación 2, aproximadamente. Aquí tienes la distribución de frecuencias para números inferiores a 10000:

La explicación de la tabla es muy sencilla: tendrán valuación 0 los números impares menores que 10000, que son 5000. Los de valuación 1 serán números doble de un impar, por lo que estos no podrán pasar de 2500. Así podemos ir razonando: valuación 2 la tendrán los números que son cuádruples de un impar, en total 1250, y así hasta el final:

En los números naturales, cada valuación presenta una frecuencia doble respecto a la siguiente (salvo redondeos)

 ¿Ocurrirá lo mismo con nuestra sucesión en la que las valuaciones se aplican sobre sumas de primos consecutivos? En principio no lo esperamos, pero vamos a experimentarlo.

Hemos recogido las valuaciones de todas las sumas tipo prime(i)+prime(i+1) menores de 50000, con este resultado:

La valuación 0 corresponde al caso 2+3.

Llama la atención que se cumple aproximadamente el hecho de que cada valor tenga el doble de frecuencia que el siguiente salvo el de 1, cuyo valor 21086 no se aproxima al doble de la siguiente, 14417. La razón es que la suma de primos del tipo 4k+1 con los de 4k+3 produce un exceso de múltiplos de 4.

En la siguiente entrada estudiaremos otros casos especiales que se pueden dar al sumar dos números consecutivos.

El juego del 2048 tiene un suelo aleatorio

Hace unas semanas comencé a jugar al 2048 (Gabriele Cirulli - http://gabrielecirulli.github.io/2048/).

Comparto la opinión mayoritaria de que es un juego adictivo y a veces desesperante. Su combinación de lógica y aleatoriedad hace que te sientas protagonista de las decisiones, pero que por otra parte temas que un 2 o un 4 aparecidos a destiempo te cierren el juego antes de lo que esperabas.

Para analizarlo mejor lo he implementado en hoja de cálculo. Esto me permite cambiar los símbolos o las reglas de juego, además de poder  idear variantes con desarrollos totalmente distintos y realizar estadísticas.

Existen bastantes páginas con consejos y estrategias para llegar a puntuaciones altas, pero en esta entrada no nos interesan, sino el estudio de la aleatoriedad contenida en el juego.

El “suelo” del juego

Cuando se desarrollan varias partidas en las mismas condiciones se observa que las puntuaciones alcanzadas fluctúan mucho de unas a otras. Según mi experiencia, si no existe un efecto de cansancio, suelen oscilar hasta 4000 puntos si se mantiene la pericia y las estrategias. Son diferencias demasiado acusadas, por lo que debemos pensar que el juego tiene un alto grado de azar.

Para aclarar la cuestión un poco se ha añadido a la implementación en hoja de cálculo el botón “Serie”, que te permite desarrollar el juego de forma aleatoria todas las veces que desees, recogiendo después las estadísticas. En un primer nivel el efecto es el de simular que la persona que juega no tiene estrategia o bien está absolutamente distraída.  A los resultados obtenidos les llamamos el “suelo” del juego, y constituyen la puntuación mínima que se debe esperar en las jugadas.

Simulación aleatoria (Nivel 1)

Para realizar un estudio fiable se ha desarrollado una serie con 1000 jugadas aleatorias. Nuestro modelo de juego las acumula en bruto, para que después se puedan analizar con las herramientas de la hoja de cálculo. Recoge puntuaciones, valor máximo conseguido y movimientos necesarios. Los resultados han sido estos:

Estadística simple

Han resultado estos promedios:

Nota: Como un consejo frecuente en este juego es el de procurar usar sólo dos direcciones en muchas fases del desarrollo, lo hemos implementado también así, que se use abajo y a la derecha de forma preferente, y, sorprendentemente, se ha incrementado algo el rendimiento, a pesar de seguir siendo un proceso aleatorio. Los resultados han subido a 83,2, 822,8 y 81,4 respectivamente. Para una muestra de 1000 intentos no están mal esas diferencias.

Así que jugando al azar sólo se llega a obtener 78,8 como valor máximo (con generosidad redondeamos al 128), muy lejos del 2048 soñado. La puntuación también es pobre, pero no tanto. Es destacable  el número de movimientos, pero es que de forma aleatoria cualquier resultado paga un precio en el exceso de los mismos.

Las desviaciones estándar de la muestra han sido:

Son llamativas, pero no tanto como esperábamos. Si usamos los máximos y mínimos, el grado de aleatoriedad aparece más claro:

Es destacable el hecho de que al jugar aleatoriamente se puedan conseguir casi 3000 puntos y llegar a 256. Por el contrario, tiene que venir la suerte totalmente en contra para llegar sólo a 16. Claro que estos son los casos extremos entre 1000 intentos.

Comparación entre variables

Valor máximo-Puntuación

Esta relación es interesante, porque nos da una medida de la cantidad de puntuaciones menores que acompañan al máximo. Podríamos sospechar que en buenos jugadores esta relación es pequeña, porque saben llegar al máximo de forma más directa, mientras que otras personas titubearán y producirán más resultados secundarios. Los resultados que ves en el gráfico se confirman con otros experimentos: la puntuación suele aproximarse a unas diez veces el valor máximo, con un ajuste bastante bueno, R^2=0,9 aproximadamente. Recuérdese que todo esto sólo es válido para jugadas totalmente aleatorias. Hemos elegido el ajuste lineal porque es el que presenta mejor valor de R^2.

Movimientos – Máximo

Esta relación no es tan fuerte, y nos presenta que para obtener un máximo determinado existe una gama muy amplia de posibles movimientos (pautas horizontales del gráfico). En promedio se consigue un valor máximo que se aproxima a una vez y media el número de movimientos.

Movimientos – Puntuación

Aquí nos encontramos con que el mejor ajuste es el potencial, con tasa de variación creciente y mayor dispersión según avanzamos en el gráfico de izquierda a derecha. Aparte de la pericia de cada persona, en el “suelo aleatorio”,  al crecer el número de movimientos se va obteniendo más rendimiento relativo y resultados más heterogéneos. La acumulación del azar abre las posibilidades.

La imagen de abajo corresponde a un cruce entre las variables Puntuación y Valor máximo (redondeadas a múltiplos convenientes). Vemos claramente que la mayor frecuencia corresponde al máximo 64 y que con ella lo más frecuente es obtener entre 300 y 600 puntos. Así que si obtienes este nivel no se te ocurra presumir.

Simulación con toma de decisiones (Nivel 2)

A nuestra simulación le añadiremos ahora un poco de inteligencia. En lugar de elegir aleatoriamente la dirección del juego, evaluaremos la ganancia en puntos que se puede lograr con un movimiento horizontal o vertical, después se elegirá uno de los dos y entre izquierda- derecha o entre arriba-abajo se tomará la decisión aleatoriamente.

Efectuadas 1000 simulaciones, hemos observado una ganancia apreciable respecto a la simulación aleatoria pura. Era de esperar, pero el incremento no llega al 100%. Sigue existiendo el “suelo” aleatorio del juego, pero más atenuado. Lo vemos en esta imagen de los resultados comparativos:

El incremento logrado en la puntuación es del 85% y en el valor máximo del 73%. Son ganancias apreciables, pero no excesivamente llamativas. Los movimientos se incrementan menos, porque la toma acertada de decisiones disminuye el número de necesarios: sólo se incrementan en un 43%. Es lógico.

También se nota el mayor rendimiento en los cocientes de comparación: por cada movimiento se logran 9,47 si jugamos de forma aleatoria y 12,24 si estudiamos antes las ganancias posibles. El proceso rinde más. La comparación con el valor máximo también se incrementa, de 1,06 a 1,28.
Como comentábamos en el Nivel 1, si sueles lograr 256 como máximo y puntuaciones de 1500 como media, estás jugando como niños de 6 o 7 años.

Comparaciones múltiples

Valor máximo – Puntuación

Sigue teniendo una buena relación lineal, con pendiente algo más baja. Es como si la pequeña inteligencia introducida lograra máximos con menos sumas secundarias, que son las que incrementan la puntuación.

Movimientos – Máximo

Aquí se nota mejor el rendimiento, que si aleatoriamente significaba un punto y medio por cada movimiento, ahora es de casi 2. También es lógico y no llama la atención.

Movimientos – Puntuación

Es muy parecida a la anterior, pero con menos dispersión en los valores mayores. Parece ser una característica del juego y no de la pericia de los jugadores.

Con esto habrás descubierto sobre qué “suelo” juegas. Vemos que existen puntuaciones mínimas que sólo son debidas al azar y que éste puede influir hasta en 3000 puntos, lo que incrementa la desesperación cuando tus planes se vienen abajo al aparecer la cifra no deseada o en la celda menos conveniente.

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 x²-a₁x-a₂=0 en el caso en el que tenga soluciones enteras.

Es fácil ver que si llamamos Z₁ y Z₂ a esas dos soluciones, deberá cumplirse que a₁=Z₁+Z₂ y a₂=-Z₁Z₂. 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)=(Z₁+Z₂)X(n-1)-Z₁Z₂X(n-2)

Por ejemplo, si deseamos generar mediante recurrencia X(n)=5ⁿ-1ⁿ, el primer paso sería elegir como a₁ su suma 6 y como  a₂ su 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)=5⁰-1⁰=1-1=0 y X(1)= 5¹-1¹=5-1=4. Lo volcamos todo en nuestra hoja de cálculo recurre_lineal y obtendremos:

Son los números de fórmula 5ⁿ-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)=mA_n+nB_n (en este caso con m y n enteros) se puede generar de esta forma:

Si X(n)=mAⁿ+nBⁿ y X(n-1)=mA^n-1+nB^n-1, tendremos X(n+1)=(A+B)*(mAⁿ+nBⁿ)-AB*(mA^n-1+nB^n-1)= (A+B-B)*mAⁿ+ (A+B-A)*nBⁿ = mAⁿ⁺¹+nB^n-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)=mAⁿ+nBⁿ se puede generar mediante una recurrencia lineal homogénea de segundo orden

Otro ejemplo

Tomemos otro ejemplo: X(n)=4ⁿ-2ⁿ. 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)=7ⁿ-(-2)ⁿ. 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 2ⁿ-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:

 a₁=3, a₂=-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 2ⁿ+3ⁿ?

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