domingo, 29 de junio de 2014

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=62. Igualmente 47+53=100=102, 71+73=144=122

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 A2-B2-C2. Por ejemplo, en el par (103049, 103067), 103067=4542-1572-2802.

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 n2-k y el otro n2+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 n2-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 km-h y km+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 k3-h y k3+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)=n2+n, es claro que será el máximo primo inferior a n2+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 42+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)2-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=962

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)

jueves, 19 de junio de 2014

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.

lunes, 9 de junio de 2014

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.