La Visión se rinde ante un Problema del Milenio

En el #6 de La Visión de Tom King y Gabriel H. Walta (el último incluido en el primer tomo de la edición española de Panini) hay una discusión muy interesante sobre el problema P vs NP. No voy a entrar a discutir las cualidades de esta magnífica serie, ya que podéis consultar si os interesan las reseñas en la Zona Negativa aquí y aquí, e iré al grano. Cuelgo las tres páginas y la coda para que admiréis el dibujo de Walta, y por si os da pereza traducir o la imagen queda muy pequeña, traduzco el texto.

  1. Como pasa a menudo, aunque trate de complejidades, el problema en si mismo no es complejo.
  2. Para simplificarlo aun más, descartaré la nomenclatura y me concentraré en los conceptos.
  3. P representa problemas que un ordenador puede resolver en una cantidad razonable de tiempo. Por ejemplo, la multiplicación. Das dos números a un ordenador, le pides que los multiplique y obtienes la respuesta muy rápido.
  4. Para obtener dicha respuesta, el ordenador no comprueba todos lo números posibles que podrían encajar en la ecuación. Eso llevaría demasiado tiempo, de tantos números que hay.
  5. No, el ordenador untilizará un algoritmo, un método, un atajo. Resuelve el problema, no adivinando al azar sino mediante un proceso ordenado.
  6. Eso es P.
  7. Problemas que son prácticos. Problemas que, usando una especie de atajo, se pueden resolver.

  1. Existe, sin embargo, otro tipo de problema. Uno para el que no hay atajos.
  2. Estos problemas tienen solución. De hecho, si tienes una solución y le preguntas al ordenador si es correcta, el ordenador te dirá si lo es o no.
  3. Sin embargo, si pides al ordenador que resuelva el problema por ti… el ordenador, sin su atajo, simplemente comprobará un número prácticamente infinito de posibilidades hasta que tropiece con la correcta.
  4. Encontrar la respuesta llevará miles de millones de años a miles de millones de ordenadores.
  5. Esto es NP.
  6. Problemas que, a efectos prácticos, simplemente no se pueden resolver

  1. La gran pregunta sobre P y NP es si son de hecho una sola cosa
  2. ¿En realidad hay atajos para todos los problemas resolubles? ¿Es que simplemente no hemos descubierto todavía estos métodos esquivos, estos algoritmos perdidos?
  3. Y si eso es cierto, si todos los problemas NP son simplemente problemas P que esperan nuestra solución… entonces un ordenador podría resolver,  a falta de un término mejor, TODO.
  4. Todos los grandes secretos, desde las colisiones de átomos hasta las colisiones de galaxias, quedarían desvelados. Los veríamos. Serían nuestros.
  5. Por el contrario, si NP no es igual a P, entonces sencillamente hay problemas –problemas con soluciones– que los ordenadores no pueden resolver.
  6. Y como tales, dadas nuestras limitaciones, las grandes cuestiones de esta vida quedarían para siempre sin respuesta.

¿Qué hace esta descripción de P vs NP en este tebeo (por cierto, titulado eso, “P vs NP”)? Muy sencillo, la Visión quiere ser normal, quiere ser feliz, quiere que su esposa e hijos (no preguntéis) sean felices. Si la felicidad es un problema P, entonces debe de haber un algoritmo sencillo, un “atajo”, como lo llaman en el texto, que nos permita encontrarla. Pero no lo encuentra, y como predice Agatha Harkness en las últimas viñetas del tebeo, la Visión va a recurrir al enfoque indeterminista: va a probar y probar y probar lo que sea para intentar encontrar la felicidad para su familia. Y el desastre está asegurado. Hasta aquí os quiero contar.

Y como aún llego a tiempo, esta entrada también participa en la Edición 8.5 del Carnaval de Matemáticas cuyo anfitrión es Raíz de 2.

Advertisements

Un problema de Marius Coman sobre raíces digitales de primos

Estaba yo pensando (es decir, buscando inspiración en Google) sobre un taller para estudiantes en que pudieran olerse conjeturas sobre números primos a partir de primos pequeños, pudieran contrastarlas con el fichero de los primeros 50 millones de primos que me generé el otro día y que ya he usado en este blog, y luego ya veríamos las que no pudieran refutar si se sabe que son verdaderas o no y cómo se podrían demostrar, cuando caí en el fascinante (por decir algo) “Two hundred and thirteen conjectures on primes” de Marius Coman (se puede descargar de aquí).

La pinta que tiene ese texto es que más o menos hace lo que quiero que hagan los niños: busca regularidades en los primeros primos, las comprueba hasta algún valor  y conjetura las que no puede refutar de esta manera. Me ha llamado la atención un problema que plantea en la página 28 sobre raíces digitales (ya sabéis, restos módulo 9) de números primos:

Hay algún otro primo p diferente de 23 con la propiedad de que, para cada una de las seis posibles raíces digitales 1,2,4,5,7,8, haya la misma cantidad de primos impares menores que p con esa raíz digital?

Está claro que un número primo no puede tener raíz digital 6 o 9 (porque entonces sería divisible por 3) y que el único primo de raíz digital 3 es el mismo 3, por lo que la podemos excluir. Entonces, los primos impares menores que 23 (y diferentes de 3) son 5, 7, 11, 13, 17, 19, de raíces digitales 5, 7, 2, 4, 8 y 1 respectivamente: una de cada. La pregunta de Coman es si vuelve a haber empate en algún otro punto de la infinita secuencia de primos.

Según el teorema de los números primos para progresiones aritméticas (podéis encontrar una demostración corta, aunque algo tramposa porque la parte difícil no la demuestra, aquí), cuando n\to \infty, las fracciones de primos menores que n con raíz digital 1,2,4,5,7 o 8 tienden a ser la misma, 1/6. En mis 50 millones de primos esto se puede detectar: si eliminamos el 2 y el 3, las frecuencias de las raíces digitales del resto de los otros 49999998 primos son

\begin{array}{l|cccccc} \mbox{R. D.} &  1  & 2  & 4  & 5  & 7 &  8  \cr \hline  \mbox{Frec.} & 8333074 & 8333893 & 8333197  & 8333574 & 8332716 & 8333544 \end{array}

La diferencia entre la frecuencia mayor y la menor en esta tabla es de 1177, que sobre unos 50\cdot 10^6 primos es una miseria.

Bueno, pues nada, que he comprobado la conjetura de Coman sobre los 49999998 primeros primos impares diferentes de 3. Y sabéis qué? Que no falla: no hay ningún empate de las seis frecuencias relativas salvo para el 23. Curioso, verdad?

(Se acerca el , así que mejor dejo algo para entonces. Continuará…)

 

Los números Le Monde-959 (por llamarlos de alguna manera)

Va, algo de precalentamiento: ¿qué números son iguales a la suma de las potencias n-ésimas (n\geq 2) de sus dos divisores más pequeños (incluyendo 1 como divisor)? Pensadlo un rato. Ah, ¿que estáis aquí para leer, no para pensar? Vaaaaale, veamos. Si N es impar, sus dos divisores menores serán 1 y un primo impar p, pero entonces N (impar) no puede ser igual a 1+p^n (par); y si N es par, sus dos divisores menores serán 1 y 2, pero entonces N (par) no puede ser igual a 1+2^n (impar).

Hechos los estiramientos, vamos al grano. En su blog, Xian (alias de Christian Robert, pero le seguiremos llamando Xian, si es lo que quiere) de vez en cuando resuelve “por fuerza bruta” problemas propuestos en Le Monde; con “por fuerza bruta” quiero decir usando un programa de R. Son unas entradas muy interesantes, porque siempre aprendo una función o un truco nuevos. En la entrada del pasado miércoles 20 de abril, Xian atacaba el problema 959, del fin de semana pasado:

Encuentra un natural A que sea igual a la suma de los cuadrados de sus cuatro divisores más pequeños (incluyendo el 1), y un natural B que sea igual a la suma de los cubos de sus cuatro divisores más pequeños. ¿Hay enteros con esta propiedad para exponentes más grandes?

Con lo que nos gusta poner nombres a los objetos, a un número con esta propiedad para un exponente n lo voy a llamar un número Le Monde-959-n. Por ejemplo, Xian encuentra un número Le Monde-959-2 (es decir, un número que es suma de los cuadrados de sus cuatro primeros divisores): 130. En efecto: 130=2\times 5\times 13 y 130=1+2^2+5^2+10^2. También encuentra un número Le Monde-959-5 (que es suma de las potencias quintas de sus cuatro primeros divisores): 17864 (podéis comprobarlo, pero en un rato lo volveremos a encontrar). Y en la solución que publicó ayer Le Monde (y que acaba de añadir Xian a su entrada)  Le Monde afirma que no hay ningún número Le Monde-959-3, y dan un número Le Monde-959-4, 1419874, y otro número Le Monde-959-5, 1015690. Como el programa de Xian es solo una prueba de concepto, solo busca hasta 10^6, por lo que no encuentra el primero. Por lo que refiere al segundo… no es suma de las potencias quintas de sus cuatro primeros divisores: 1015690=2\times 5\times 13^2\times 601 \neq 1+2^5+5^5+10^5.

Naturalmente, uno se puede preguntar si hay más números con esta propiedad. La base de la cacería será la siguiente. Si N fuera un número Le Monde-959-n impar, sus cuatro primeros divisores serían impares y por lo tanto la suma de sus potencias sería par, por lo que no podría ser igual a N. Así pues, todo número Le Monde-959-es par y sus dos primeros divisores serán 1 y 2. Ahora bien, como 1+2^n es impar, para que la suma de las potencias de los cuatro divisores más pequeños sea par, el tercer y el cuarto han de ser de paridades diferentes. La conclusión es que los números Le Monde-959-solo pueden tener una de las dor formas posibles, para algún primo impar p:

A_{n,p}=1+2^n+4^n+p^n o B_{n,p}=1+2^n+p^n+(2p)^n=(1+2^n)(1+p^n)

Esto nos permite buscarlos. Por ejemplo, para n=2, ha de pasar:

  • Si es del tipo A_{n,p}, p ha de dividir a 1+2^2+4^2=21, por lo que p=3 o p=7, y 4 ha de dividir a 1+p^n, que no pasa para ninguno de los dos.
  • Si es del tipo B_{n,p}, p ha de dividir a 1+2^2=5, es decir, p=5 y obtenemos el 130.

Así pues, el único número Le Monde-959-2 es 130. Bien. En general, no hay soluciones del tipo A_{n,p} con n par, porque en este caso 4 nunca divide a 1+2^n+4^n+p^n.

Qué pasa con n=3? Repetimos razonamiento:

  • Si es del tipo A_{n,p}, p ha de dividir a 1+2^3+4^3=73, por lo que p=73, pero entonces 1+2^3+4^3+73^3=389090 no es es divisible por 4
  • Si es del tipo B_{n,p},  p ha de dividir a 1+2^3=9, es decir, p=3, pero entonces 1+2^3+3^3+6^3=252 es divisible por 4, por lo que 6 no es uno de sus cuatro divisores más pequeños.

Así pues, no hay números Le Monde-959-3. Seguimos coincidiendo.

Otro más, y luego ya os dejo con resultados generales. ¿n=4? Ya sabemos que no hay soluciones de la forma A_{n,p}. En una solución del tipo B_{n,p}, p ha de dividir a 1+2^4=17, es decir, p=17, y resulta que 1+2^4+17^4+34^4=1419874=2\times 17\times 41761, por lo que 1419874 es el único número Le Monde-959-4.

Y en general? Vale, os dejo como ejercicio sencillo los tres resultados siguientes:

  1. Si n=4m+2, entonces los números B_{n,5}=1+2^n+5^n+10^n son siempre Le Monde-959-n. Cuando m=0, B_{2,5}=130, cuando m=1, B_{6,5}=1015690 = 2\times 5\times 13^2\times 601. La demostración general (que 3, 4 y 7 no dividen a B_{n,5} y 5 sí) es sencilla.
  2. Si n=4m con m impar (es decir, n=8k+4), entonces los números  B_{n,17}=1+2^n+17^n+34^n son siempre Le Monde-959-n. Cuando m=1, B_{4,17}=1419874, dado por Le Monde; cuando m=3, B_{12,17}=2387003305930334914 = 2\times 17\times 73\times 241\times 1321\times 41761\times 72337 . De nuevo, la demostración general (que 3, 4, 5, 7, 11,  13, 19, 23, 29, 31 no dividen a B_{n,17} y 17 sí) es sencilla, pero algo larga a mano.
  3. Si n es impar pero no múltiplo de 3, entonces A_{n,7}=1+2^n+4^n+7^n son siempre Le Monde-959-n.  Cuando n=5, A_{5,7}=17864, el que encontró Xian; cuando n=7, B_{7,7}=840056 = 2^3\times 7^2\times 2143. La demostración general (que 3 y 5 no dividen a A_{n,7} y 4 y 7 sí) también es sencilla y esta vez corta.

Qué pasa con los otros exponentes? Ya hemos visto que no hay números Le Monde-959-3, y un argumento similar muestra que tampoco hay números Le Monde-959-9. No he sabido demostrar que, en general, no hay números Le Monde-959-con n múltiplo impar de 3, pero tiene toda la pinta (va, conjetura).

¿Y los números Le Monde-959-con n múltiplo de 8? Para n=8 no existe ninguno: 1+2^8=257 es primo y B_{8,257} no funciona; para n=16 sí que existe uno: B_{16,65537}, que no copio aquí porque es un monstruo; para n=24 no existe ninguno; para n=32, existe uno: B_{32,641}; para n=40 no existe ninguno; para n=48, existe uno: B_{32,257}. La pauta es clara, pero tampoco lo he sabido demostrar.

En general, podríamos preguntar

¿Para qué números naturales k\geq 3 y n\geq 4 existen números naturales N que son iguales a la suma de las potencias n-ésimas de sus primeros k divisores?

Para k=3 es fácil (para n par, nunca; para n impar, 1^n+2^n+3^n siempre; ejercicio). El resto, lo dejo para algún fan del Problema de Waring.

Vaya, se me ha terminado la entrada y no hay ninguna imagen. Va, unos gatitos para alegraros el dia

kittens

Y, siempre con el tiempo justo, esta entrada participa en la Edición 7.3 del Carnaval de Matemáticas, cuyo anfitrión es pimedios.

 

¿Y qué pasa con las penúltimas cifras?

Pensando en el sesgo detectado en las frecuencias de las últimas cifras de los primos que siguen a un primo de última cifra fijada, me preguntaba qué pasaba con las penúltimas cifras. Como en Mallorca esta semana aún estamos de vacaciones escolares (envidia cochina), he hecho un programilla en R para mirarlo. He creado una lista con los primeros 50 millones de primos (no, esta vez no la voy a colgar en el dropbox, ocupa más de 500 Mb; si os da pereza generarla, la podéis descargar con paciencia de “The first fifty million primes”), para cada uno de ellos me he quedado con su penúltima cifra y he calculado

  • la frecuencia relativa de esta penúltima cifra
  • la frecuencia con que una penúltima cifra de primo sigue a otra penúltima cifra de primo

Y los resultados son curiosos, al menos para mi teoría de números.

Vamos con las primeras: no hay sorpresas, cada penúltima cifra aparece aproximadamente en un 10% de los primos, con diferencias de más o menos 5 milesimas de punto porcentual.

Pero en las frecuencias condicionadas hay sorpresa, y además sorpresa regular: Si la penúltima cifra de un primo es x, entonces, independientemente de x, la probabilidad de que la penúltima cifra del siguiente primo sea (módulo 10)

  • x, es de un 16.7%
  • x+1, de un 33.4%
  • x+2, de un 21.1% o un 21.2%
  • x+3, de un 14.1%
  • x+4, de un 6.5%
  • x+5, de un 3.7% o un 3.8%
  • x+6, de un 2.4%
  • x+7, de un 1.1%
  • x+8, de un 0.6%
  • x+9, de un 0.4%

La tabla concreta, para 50 millones de primos, es

2016-03-29 09.58.10

Además, estas proporciones van variando a medida que tomamos más números primos, pero  siempre son más o menos independientes de la penúltima cifra x del primo “antecedente”.

Podéis descargar de aquí el fichero html con los resultados (las tablas para los primeros 10, 20, 30, 40 y 50 millones de primos), y de aquí el fichero Rmarkdown que lo ha producido (pero para ejecutarlo, necesitáis la lista de primos).

Ya digo, supongo que hay algún teorema que implique este comportamiento de las penúltimas cifras, pero mi teoría de números está oxidada.

 

Poussy tiene un problema

Poussy es un gatito protagonista de unas tiras cómicas publicadas por Peyo (el padre de los Pitufos, de Johan y Pirluit, o de Benito Sansón, Benet Tallaferro para los que lo leíamos en Cavall Fort) entre 1949 y 1992, con diversos parones y delegando al final en miembros de su estudio. Durante mucho tiempo los tres álbumes que recogían sus aventuras han estado agotados y eran carne de coleccionista, pero, por suerte, al fin se ha publicado, en 2014 en Francia y en 2015 en España (tanto en catalán como en castellano) una edición integral de sus gags.

 

Hoy os traigo un problema a la Dan Meyer. Se trata de la tira número 72. El problema es: ¿A qué altura está colgado el jamón? (Clicad en la imagen para ampliarla)

poussy

Con esta entrada, Poussy y yo participamos en  la Edición 7.2 del Carnaval de Matemáticas que alberga La Aventura de la Ciencia.