La conjetura de Brocard

La conjetura de Brocard indica que hay siempre al menos 4 primos entre n2 y (n + 2)2

Puede observarse que el enunciado de esta conjetura es muy similar a la de Legendre, por lo que una argumentación parecida tal vez podría resolverla.

En efecto, parece que como (n + 2)2 – n2  = 4n + 3, si tenemos en cuenta que las cribas del 9, 25, 49 y 121 no se aplican por ser cuadrados de primos y que se verifica para números menores de 121, el argumento sigue siendo válido cambiando algunos valores en nuestra demostración de la conjetura de Legendre.

En esta tabla se ve que los números menores de 121 cumplen la conjetura:

N N+2 N^2 (N+2)^2 p1 p2 p3 p4
1 3 1 9 2 3 5 7
2 4 4 16 5 7 11 13
3 5 9 25 11 13 17 19
4 6 16 36 17 19 23 29
5 7 25 49 29 31 37 41
6 8 36 64 37 43 47 53
7 9 49 81 53 59 61 67
8 10 64 100 67 71 73 79
9 11 81 121 83 89 97 101
10 12 100 144 101 103 107 109

 

El número primo más grande jamás encontrado

Hasta hoy el mayor número primo registrado es un número primo de Mersenne de 22.7 millones de cifras.

Si tomamos 1MM como un millón, el siguiente número es primo con una probabilidad del 99,99%:

10 ^ 100MM + 3.

¿El motivo? Cuando realizamos una factorización de un número para ver si es primo o no, lo primero que hacemos es:

  •  Ver su última cifra: si es par, es divisible por 2 y por tanto no es primo, si es 5, es divisible por 5 y tampoco sería primo.
  • Luego sumamos todas sus cifras y vemos que no sean múltiplos de 3, ya que si lo son, entonces es divisible entre 3.
  • Luego sumamos las cifras en posiciones pares por un lado y las cifras en posiciones impares por otro, realizamos la diferencia y vemos que no sea un múltiplo de 11, ya que si no, sería múltiplo de 11.
  • Si ninguno de los criterios anteriores funciona, empezamos a dividir entre los números primos menores que el número que queremos saber si es primo o no empezando por el menor que no hayamos probado, es decir, empezando a dividir por 7, luego por 13, luego por 17… y así hasta la raíz cuadrada del número a comprobar. ¿Por qué por el menor? Porque a medida que vamos probando posibles divisores, si no encontramos un divisor primo, la probabilidad de que este número sea primo aumenta.

Nuestro número, 10 ^ 100MM + 3 no termina en 2 par, luego no es divisible por 2.

Tampoco termina en 5, luego no es divisible por 5.

La suma de sus cifras es 4, luego no es divisible por 3.

El criterio de divisibilidad del 11 tampoco se cumple, luego no es divisible por 11.

Si probamos a dividir por 7, vemos que los restos se repiten cada 6, luego en el algoritmo de la división, la cifra que bajamos del cociente también se repetirá cada 6. Esto nos da que la ultima bajada de cifra es 3 con 4 de resto, y 43 no es divisible por 7.

Si probamos a dividir por 13, vemos que los restos se repiten cada 6 y tenemos que 33 no es divisible por 13.

Con 17, cada 15 y el último resto añadiéndole 3 (13) no es divisible por esta cifra.

Podemos seguir cuanto queramos: si seguimos hasta 10 ^ 50 MM + 1, que sería su raíz cuadrada, estaríamos 100% seguros de que es primo, pero la experiencia nos dicta que un número impar seleccionado al azar de entre todos los posibles números que terminen en 1, 3, 7 y 9 es primo con certeza casi absoluta si probamos todos los primos menores de 100 y no encontramos ninguno que lo divida.

¿No sé cree que este número sea primo? Pues yo tampoco me creo que el número de Mersenne 274,207,281-1 de más de 22 millones de cifras sea primo por mucho que David Stanfill y Serge Batalov digan que lo han verificado en 3,5 días, por la sencilla razón de que, si somos rigurosos, tendrían que haber verificado si es divisible entre todos los primos menores de 11 millones de cifras y esto consumiría más energía que la que todos los átomos de Uranio del universo en una central adaptada para ello nos podría proporcionar. Y si no, trate de escribir ese número a mano y luego hablamos.

Por mi parte, en caso de que mi número dado no sea primo, si tenemos en cuenta los resultados de una anterior entrada respecto a la conjetura de Andrica, como parece que hay una cota entre números primos, si ese no es, se podrían revisar los siguientes, no sé, digamos que 200.000 números que terminen en 1, 3, 7 y 9. ¿Le parecen muchos 200.000 números? ¿Y 10 ^ 100 MM + 3 no? Allá usted.

La conjetura de Andrica y otra de mi invención

La conjetura de Andrica está relacionada con los números primos y trata de ver que espacios hay entre ellos a medida que los vamos generando.

Dice que si p(n) es el n-ésimo número primo y p(n+1) el siguiente mayor que él, la diferencia de sus raíces cuadradas es menor que 1, e.d., raíz(p(n+1)) – raíz(p(n)) < 1.

Curioseando con una tabla, he llegado a mi siguiente conjetura:

p(n+1) < 4 + p(n) + raíz(p(n))

Afinando un poco más la cota, la doy en 2 tramos:

p(n+1) < 4 + p(n) + (9/10) * raíz(p(n)) si p(n)< 2400

y

p(n+1)< 35 + p(n) + (9/10) * p(n) ^ (37/100) si p(n) >= 2400

Excepto para el 3, 5 y 7, se reduce el espacio de búsqueda del siguiente primo (gap en inglés) en hasta más de 10 veces para los primeros 65.000 primos.

El problema es encontrar un método general para verificar la conjetura para primos mayores, porque según el teorema de Euclides son “infinitos” (utilizando la reducción al absurdo), aunque parece que yo estaré finado antes de ver mi conjetura demostrada y con el nombre de Teorema en lugar de Conjetura.

Little Chess

¿Conoce las reglas del ajedrez? Pues imagine un tablero más pequeño y con menos piezas. No lo imagine, se lo dibujo yo:

Minichess

Los movimientos de las figuras (torre, peón, dama y rey) son los mismos del ajedrez. Si utilizamos la notación algebráica reducida a este tablero, tenemos que las torres blancas están situadas en las casillas a1 y d1, los peones blancos en las casillas a2, b2, c2, y d2, etc.

Si mueven primero las blancas, ¿cuál sera el resultado del juego si ambos bandos juegan corréctamente (ambos quieren ganar y realizan el mejor movimiento posible en cada turno)?

Utilizando la notación algebráica, tenemos:

1. axb3+, Dxb3 (única)

2. cxb3, Rb4 {si Rxb3, 3. Da2+, Rb4 (única) 4. bxa3+, Txa3 (única) 5. Dxa3+, Rc4 (única) 6. Da4++}

3. bxa4=D+, Rxa4 (única)

4. Txa3+, Rb4 (única)

5. Da2, {5. bxc3+, Rxa3 (5. …, Rc4, 6. Db4++ ó 6. Da2++) 6. Db2+, Ra4 (única) 7. cxd4=D++ }

5. …,cxb2+ { 5. …, Tc4 6. Db3++ }

6. Dxb2+, Rc4

7. Db3++ (ó Dc3++ ó Ta4++)

 

y por tanto mate en 7 con la mayor parte de los movimientos de las negras forzados.

Esto nos indica que el juego tiene solución y que esta solución es VICTORIA DE LAS BLANCAS, aunque, ¿hay alguna forma de llegar al jaque mate que emplee menos movimientos teniendo en cuenta que el jugador de negras hará todo lo posible por no perder? Parece que no. También se puede llegar al jaque mate de otras maneras, pero como son necesarios más movimientos que de esta forma, desde el punto de vista de la Teoría de Juegos las consideramos erróneas (peor estrategia).

Si tratamos el ajedrez de esta misma manera, tenemos que la solución del mismo tiene que ser una de las siguientes: VICTORIA DE LAS BLANCAS, VICTORIA DE LAS NEGRAS o TABLAS y consideraríamos error cualquier movimiento que no llevara a ese resultado en el menor número de movimientos posibles.

Para evaluar posibles combinaciones que den lugar a cambios de piezas, los grandes maestros consideran, y así enseñan, que estas tienen cierto VALOR MATERIAL: peón=1, caballo = alfil = 3, torre = 5, dama = 9, rey = “infinito” (aunque no hay consenso en el valor de las mismas).

Pensemos un momento en el “miniajedrez” propuesto al principio de esta entrada: ¿tiene sentido allí ese concepto de VALOR MATERIAL? Obviamente, NO, ya que el resultado es una combinación con al menos 3 MOVIMIENTOS FORZADOS para las negras.

¿Habrá una combinación de n movimientos, con n finito que nos lleve al jaque mate de blancas a negras, negras a blancas o tablas? Como es un “juego” de información perfecta, tiene que haberla. En tal caso, ¿Cuál es? ¿Cuánto vale n? ¿Ganan blancas, negras o es tablas?

En mi opinión, si algún ser racional es capaz de demostrarlo, habrá resuelto uno de los problemas del milenio de las matemáticas: mucho más importante que los de las clases de complejidad P vs NP, que la hipótesis de Poincaré o que la de Riemann referida a los números primos dado que a diario se juegan millones de partidas de ajedrez en todo el mundo. En lo que a mí respecta, según los cálculos del campeón del mundo de ajedrez Max Euwe, seguramente estaré muerto antes de que dicha solución sea publicada.

Ajedrez desde el punto de vista matemático

Siguiendo la teoría de juegos, vemos que el ajedrez se encuentra clasificado como juego no cooperativo de información perfecta y que por lo tanto, en teoría (valga la redundancia) partiendo de la posición inicial, se podría saber de antemano quien va a ganar una partida si los dos jugadores hacen las jugadas correctas o si el resultado es un empate.

Con estas premisas, cuando analizamos una partida cualquiera que ya se haya jugado, podemos inferir que si ha finalizado por jaque mate, ha sido porque alguno de los contendientes realizó una jugada incorrecta o bien porque dada la posición de las fichas en el tablero, si se jugaba correctamente por parte de los dos bandos (ya sea por ventaja material y/o posicional), el resultado no podía ser otro.

Los casos en los que quedan pocas piezas sobre el tablero (4, 5, 6 y 7) se han estudiado en profundidad y se sabe una solución exacta de los mismos mediante las tablas de Lomonosov, en las que no hay mas que realizar los movimientos que nos llevan a la victoria en la menor cantidad de pasos o bien los movimientos que llevan al empate seguro (cualquier movimiento que se salga de estas tablas y que no lleve al empate, se considera un error). El problema es que el almacenamiento de estas tablas ocupa 140 Terabytes (sí, 140 discos duros de 1 Terabyte, o 70 de 2 Terabytes, o la proporción que sea), por lo que para un humano, aprenderse de memoria todas las combinaciones sería en principio impracticable.

Los grandes maestros de ajedrez han establecido una valoración de las piezas en función de su movilidad para la hora de hacer cambios (dama = 9 peones, torre = 5 peones, alfil = caballo = 3 peones). Pensando como programador de ordenadores, me imagino que los programas de ordenador que juegan al ajedrez establecen cuales son las mejores combinaciones mediante el método del simplex minmax recorriendo árboles de decisión con alguna función objetivo, aunque en esos árboles también considerarían si hay una combinación de mate en pocas jugadas y priorizarían estas combinaciones ante las de ganancia de material.

Actualmente los mejores programas tienen mejor ELO que los mejores humanos jugadores de ajedrez (ELO es un sistema de valoración de fuerza de juego propuesto por un físico y basado en cuestiones de probabilidad).

Obviamente, si tuviésemos la solución del juego, esta valoración de piezas no valdría absolutamente para nada porque bastaría seguir la mejor línea (que nos lleve a la victoria en un menor número de pasos , al empate o a la derrota en un mayor número de pasos esperando el fallo del rival). De hecho ni siquiera existe consenso entre los grandes maestros de ajedrez en el valor de las mismas (otros dan valor de 10 peones a la dama, otros de 5.5 a la torre, otros de 3.5 al alfil…).

Como ejemplo de juego de información perfecta tenemos las 3 en raya, dónde si se comienza correctamente, el primer jugador pone su ficha (aspa o círculo) en el centro y el contrario, si comienza correctamente, pone su ficha (círculo o aspa) en una de las esquinas, ya que si no, el contrario puede ganar la partida.

He leído que hay grupos de trabajadores de Google y Facebook que están buscando aplicar “Inteligencia Artificial” para hallar una solución de otro juego milenario, el Go. Ruego que cuando la encuentren, por favor, me avisen.

Polinomios

No me extiendo:

Tenemos el polinomio atribuido a Euler, f(x) = x*x + x + 41, que si le damos valores a la x variando entre 0 y 39, nos da 40 números distintos que son primos.

Yo he sacado este otro: f(x) = x*x + 3*x +43, que si le damos valores a la x variando entre 0 y 38, nos da 39 números distintos que son primos.

Este polinomio da los mismos números primos que el de Euler exceptuando el 41… ¿Habrá alguna regla general para construir este tipo de polinomios?