lunes, 7 de julio de 2014

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.

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.

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)