Blioquinfo

La Visión se rinde ante un Problema del Milenio

July 6, 2017July 6, 2017Cesc1 Comment

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.

Como pasa a menudo, aunque trate de complejidades, el problema en si mismo no es complejo.
Para simplificarlo aun más, descartaré la nomenclatura y me concentraré en los conceptos.
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.
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.
No, el ordenador untilizará un algoritmo, un método, un atajo. Resuelve el problema, no adivinando al azar sino mediante un proceso ordenado.
Eso es P.
Problemas que son prácticos. Problemas que, usando una especie de atajo, se pueden resolver.

Existe, sin embargo, otro tipo de problema. Uno para el que no hay atajos.
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.
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.
Encontrar la respuesta llevará miles de millones de años a miles de millones de ordenadores.
Esto es NP.
Problemas que, a efectos prácticos, simplemente no se pueden resolver

La gran pregunta sobre P y NP es si son de hecho una sola cosa
¿En realidad hay atajos para todos los problemas resolubles? ¿Es que simplemente no hemos descubierto todavía estos métodos esquivos, estos algoritmos perdidos?
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.
Todos los grandes secretos, desde las colisiones de átomos hasta las colisiones de galaxias, quedarían desvelados. Los veríamos. Serían nuestros.
Por el contrario, si NP no es igual a P, entonces sencillamente hay problemas –problemas con soluciones– que los ordenadores no pueden resolver.
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.

Con dos tiradas suele bastar

July 2, 2017Cesc1 Comment

¿Quieres que nos juguemos el café? Mira, vamos a lanzar un dado por turnos e ir sumando los resultados que vayamos obteniendo. Gana el primero que con su tirada pase del número de caras del dado. Llevo mis dados de Magic en el bolsillo, vamos a usar el de 20 para añadir un poco de emoción, así que ganará el primero que llegue a 20. ¿Vale? Empiezas tú. Tiras, sacas un 7, no llegas a 20. Tiro yo, saco un 6: 7+6=13, no llego a 20, tira. Sacas un 12: 13+12=25, ganas. ¡Mier…,! ¡Uy, perdón, eso sí que no me lo esperaba! ¿Al mejor de tres?

(2 horas antes)

Estaba leyendo la autobiografía matemática de John Allen Paulos y en un momento dado cita un artículo suyo en ABCnews con apariciones estelares (la primera, literalmente) del número e. Una de ellas es, traduzco (y abrevio):

John Allen Paulos

Escoger números al azar también puede dar lugar a e. Elige un número entero aleatorio entre 1 y 1000. (Digamos que escoges 381.) Elige otro número aleatorio (digamos 191) y súmalo al primero (en este caso, da 572). Continua eligiendo números aleatorios entre 1 y 1000 y sumándolos a la suma de los números aleatorios escogidos previamente. Detente sólo cuando la suma supere los 1000. (Si el tercer número fuera 613, por ejemplo, la suma pasaría de 1000 después de tres selecciones.)

¿Cuántos números aleatorios, en promedio, necesitarás elegir? En otras palabras, si un grupo grande de personas repite este procedimiento, generar números entre 1 y 1000 y sumarlos hasta que la suma pase de 1000 y registrar el número de selecciones que han necesitado para llegar superar el 1000, el número promedio de dichas selecciones sería –lo has adivinado– muy próximo a e.

Pues sí, en la página del Wolfram Mathworld sobre la distribución de sumas de copias de una variable uniforme en [0,1] encontraréis la demostración de que si vais tomando números al azar entre 0 y 1 con distribución uniforme y sumándolos, la probabilidad de que la primera elección en la que la suma sea $\geq 1$ sea la n-ésima es $1/(n(n-2)!)$ y de que, entonces, la esperanza de esta distribución de probabilidades, es decir, el número promedio de números que tendremos que tomar para superar el 1, es e. Multiplicando por 1000, y quitando partes decimales, obtenéis la aproximación citada por Paulos.

Naturalmente, aunque lanzar un dado de N caras sea escoger un número entero al azar (y equiprobablemente) entre 1 y N, si N es pequeño entonces los decimales que se borran juegan un papel importante. Por ejemplo, con un dado de 6 caras, el número medio de lanzamientos necesarios para sumar 6 o més es un poco más de 2.16, y con un dado de 20 caras para superar el 20 necesitamos en promedio un poco más de 2.52. Con el dado de 100 caras que todos los matemáticos tenemos en casa rondamos el 2.68.

Pero hay otro dato que me interesa en el juego de tirar el dado y sumar hasta superar el umbral: si jugamos con un dado de N caras, más de la mitad de las veces llegaremos a N en la segunda tirada, independientemente de N. Esta probabilidad es muy sencilla de calcular: para pasar de N en la segunda tirada pero no en la primera, tenemos que sacar un k entre 1 y N-1 en la primera tirada y luego en la segunda cualquiera de los k+1 valores que hacen que la suma supere N (por ejemplo, si con un dado de 20 caras en la primera tirada saco un 5, para llegar a 20 en la segunda necesito algo entre 15 y 20). Por tanto, de las $N^2$ posibles tiradas dobles, en $\sum\limits_{k=1}^{N-1} (k+1)=(N+2)(N-1)/2$ pasaremos de N sin que en la primera tirada lleguemos a N, y este número es mayor que $N^2/2$ si $N\geq 3$ . En concreto, la probabilidad de superar N en dos tiradas de un dado de N caras es de aproximadamente 0.56 si N=4 o N=6; 0.53 si N=12; y 0.52 si N=20.

Así que en el jueguecito del principio, si dejamos empezar al otro, lo más probable es que ganemos en la segunda jugada, independientemente del dado. Y si no, siempre nos queda la cuarta, la sexta…

-Hola, Cesc, te veo muy concentrado

-¡Hola! Sí, estaba haciendo unos cálculos. Oye, ¿quieres que nos juguemos el café? Mira, vamos a lanzar un dado por turnos…

Esta entrada participa en la Edición 8.5 del Carnaval de Matemáticas cuyo anfitrión es Raíz de 2.

¿Cuántas hojas tiene el árbol 2017?

May 25, 2017May 26, 2017Cesc2 Comments

¿Conocéis el chiste aquel de los dos presos que hace mucho tiempo que comparten celda, y va uno y le pide al otro “Va, cuéntame un chiste”, el otro contesta “El 56” y el primero se parte de risa? Pues últimamente yo estoy en la tesitura de “Va, dame un árbol”, y ya me va bien que me den el 56, pero claro, luego he de saber cuál es. En última instancia, numerar objetos es una manera de ponerles nombre y por lo tanto de poseerlos. Pero entonces es necesario un diccionario que nos permita recuperar los objetos a partir de los números, y si ese diccionario se puede reducir a un algoritmo sencillo, mejor.

En el caso de los árboles (en lo que sigue, por un “árbol” entiendo un árbol en el sentido de la teoría de grafos y con raíz, que en los dibujos corresponde al nodo superior), hay una numeración muy útil: los números de Matula, que se definen recursivamente de la manera siguiente. Si $T$ es un árbol de un solo nodo, $M(T)=1$ . Si $T$ tiene más de un nodo y $T_1,\ldots,T_k$ son los subárboles que cuelgan de los hijos de su raíz y $m_1=M(T_1),\ldots, m_k=M(T_k)$ son los números de Matula de estos subárboles y $p_{m_1},\ldots,p_{m_k}$ son los primos $m_1$ -ésimo, $m_2$ -ésimo, …, $m_k$ -ésimo, entonces $M(T)=p_{m_1}\cdots p_{m_k}$ .

Veamos un ejemplo. Considerad el árbol de la figura, lo llamaremos T (y como hoy es el día del orgullo friki, uso Comic Sans).

Para calcular su número de Matula, hemos de calcular los de sus subárboles T1 y T2. El de T2 és fácil: 1, porque es un solo nodo (una hoja). El número de Matula de T1 será el producto de los primos correspondientes a los de T3 y T4, así que necesitamos calcular primero los números de Matula de T3 y T4. Veamos: la raíz de T3 tiene 3 hijos y los tres son hojas, por lo que cada uno define un subárbol de un solo nodo; por lo tanto, cada uno de estos subárboles tiene número de Matula 1, y como el primer primo es $p_1=2$ , tenemos que $M(T3)=p_1\cdot p_1\cdot p_1=2\cdot 2 \cdot 2=8$ . Por otro lado, la raíz de T4 tiene 2 hijos, los dos hojas, por lo que cada uno define un subárbol de un solo nodo, de número de Matula 1. Obtenemos entonces que $M(T4)=p_1\cdot p_1=2\cdot 2=4$ .

Como T3 y T4 son los árboles número 8 y 4, respectivamente, por la recurrencia, $M(T1)$ será el producto del octavo primo, $p_{8}=19$ , y del cuarto primo, $p_4=7$ : $M(T_2)=19\cdot 7=133$ . Y como $M(T2)=1$ , tenemos finalmente que $M(T)$ será el producto del primo en la posición 133, $p_{133}=751$ y del primer primo, $p_1=2$ . Es decir, $M(T)=751\cdot 2=1502$ .

Este proceso se puede invertir. Dado un número $N$ , lo descomponemos en producto de números primos $N=q_1\cdots q_m$ y buscamos cuál es el número de orden de cada $q_i$ en la lista de todos los primos: digamos que cada $q_i$ es el primo $m_i$ -ésimo. Entonces, la raíz de el árbol T $M(T)=N$ tendrá m hijos, y de ellos colgarán los árboles $T_i$ número $M(T_i)=m_i$ . Naturalmente, si $N=1$ entonces T es el árbol de un solo nodo, por definición.

Por ejemplo, ¿cuál el es árbol 2017? 2017 es primo, en concreto $p_{306}$ . Por lo tanto el árbol 2017 estará formado por una raíz de la que cuelga un solo hijo, que es la raíz del árbol número 306. Ahora $306=2\cdot 3\cdot 3 \cdot 17$ . Como $p_1=2$ , $p_2=3$ y $p_7=17$ , el árbol 306 está formado por una raíz de la que cuelgan 4 hijos, que son raíces de un árbol número 1 (un solo nodo), dos árboles número 2, y un árbol número 7. Os dejo terminar: el árbol número 2 está formado por una raíz con un único hijo que además es una hoja, y el árbol número 7 ( $=p_4$ ) está formado por una raíz con un único hijo del que cuelgan dos hijos que son hojas. El resultado es el de la figura que sigue.

Por lo tanto, cada árbol tiene su número y cada número (natural y a partir de 1) representa un único árbol. Ya los tenemos numerado. Pero además, muchas propiedades de un árbol se pueden obtener a partir de su número, sin tener que reconstruir el árbol. Por ejemplo, su número de hojas. Es fácil comprobar, siguiendo la reconstrucción de un árbol a partir de su número, que si llamamos $N(T)$ al número de hojas de T e indicamos por $T_n$ el árbol número $n$ , entonces

$N(T_1)=1$ ,
$N(T_n)=N(T_m)$ si $n=p_m$
$N(T_n)=N(T_{q_1})+\cdots+N(T_{q_k})$ si $n=q_1\cdots q_k$ y $k\geq 2$

Por ejemplo, el número de hojas de nuestro árbol T número 2017 es $N(T_{2017}) =N(T_{306}) =N(T_{2\cdot 3\cdot 3 \cdot 17}) =N(T_2)+2N(T_3)+N(T_{17})=N(T_2)+2N(T_2)+N(T_{7})=3N(T_2) +N(T_4)=3N(T_2) +2N(T_2)=5N(T_2)=5N(T_1)=5$

¡Bien!

Otros muchos índices de un árbol se pueden calcular de manera recursiva a partir de su número de Matula. De hecho, ya os podéis imaginar que todo lo que se pueda calcular recurrentemente de hijos a padres se podrá determinar a partir del número de Matula. Si os interesa, este artículo de E. Deutsch explica la manera de calcular una trentena de índices.

Esta entrada participa en la edición 8.4 del Carnaval de Matemáticas, cuyo blog anfitrión es matematicascercanas.

Carreras de raíces digitales de primos

May 25, 2016May 25, 2016Cesc2 Comments

En su famoso artículo “Prime Number Races” (The American Mathematical Monthly, 2006; encontraréis la versión española en la Gaceta de la RSME aquí), A. Granville y G. Martin popularizaron las carreras de primos, que ya habían sido introducidas por Knapowski y Turán en una serie de artículos en Acta Arithmetica a mediados de los años 1960. Por una carrera de primos no me refiero a que en alguna fiesta familiar se organize una carrera en la que participen todos los nietos del patriarca. No. En nuestras carreras de primos, se fija un módulo (por ejemplo, 4) y cada participante escoge un resto para ese módulo que sea coprimo con él (por ejemplo, yo escojo el 1 y tú escoges el 3). Entonces, a medida que se va recorriendo la lista de números primos, cada resto que aparece suma 1 al que lo ha escogido. Al final, cuando se llega a la meta prefijada, gana el participante cuyo resto haya aparecido más veces: ¿Que han salido más unos? Gano yo. ¿Más treses? Ganas tú. ¿Empate? Empate.

Los resultados que se conocen sobre carreras de primos son fascinantes, y se remontan al trabajo de Littlewood sobre el Teorema de los números primos. Fijemos algunas notaciones, para abreviar el lenguaje. Denotaremos por $\pi(n;q,a)$ el número de primos $\leq n$ que son congruentes con $a$ módulo $q$ ; supondremos siempre que $a$ y $q$ son coprimos, aunque no lo digamos explícitamente. Recordemos, además, que $\pi(n)$ indica el número de todos los primos $\leq n$ . Por ejemplo, siguiendo con los primos módulo 4, $\pi(n; 4, 1)$ y $\pi(n;4,3)$ son los números de primos menores o iguales a $n$ que son congruentes con 1 y con 3 módulo 4, respectivamente.

El teorema de los números primos para progresiones aritméticas que citaba en un post anterior garantiza que, cuando $n\to \infty$ , la fracción $\pi(n; q,a)/\pi(n)$ tiende a $1/\phi(q)$ (donde $\phi$ es la función de Euler que nos da el número de restos módulo $q$ coprimos con este). Por ejemplo, a medida que $n$ tiende a infinito, los primos $\leq n$ congruentes con 1 módulo 4 tienden a ser la mitad, y los congruentes con 3 módulo 4 la otra mitad.

Ahora bien, la pregunta relevante para nuestras carreras de primos es ¿cómo se van comportando las cantidades $\pi(n; 4, 1)$ y $\pi(n;4,3)$ a medida que $n$ crece? ¿Quién tiene más probabilidades de ganar una carrera?

Ya en 1835, Chebyshov (¿ahora se escribe así?) mencionaba en una carta que parecía haber muchos más primos congruentes módulo 4 con 3 que con 1 (el famoso sesgo de Chebyshov). De hecho, la primera vez que $\pi(n; 4, 1)>\pi(n;4,3)$ es en $n=26861$ y luego no vuelve a pasar hasta $n=616841$ . No obstante, un teorema de Littlewood garantiza que el signo de $\pi(n; 4, 1)- \pi(n;4,3)$ cambia infinitas veces, así que hay infinitas ocasiones en que en las que el 1 gana al 3.

Ahora bien, si la Hipótesis generalizada de Riemann y la Conjetura de Independencia Lineal LI de los ceros de $\zeta(x)$ son verdaderas, Rubinstein y Sarnak demostraron en 1994 que, en un cierto sentido específico, la “probabilidad” de que $\pi(n; 4, 3)$ sea mayor que $\pi(n;4,1)$ es del 99.6%. Más en general, el teorema de Rubinstein y Sarnak dice que

si $a$ y $b$ son ambos cuadrados o ambos no cuadrados módulo $q$ , la “probabilidad” de que $\pi(n; q,a)>\pi(n; q,b)$ es 0.5

si $a$ no es un cuadrado módulo $q$ y $b$ sí, la “probabilidad” de que $\pi(n; q,a)>\pi(n; q,b)$ es mayor que 0.5 (y puede ser mucho mayor, como vemos para $q=4$ )

Así que, ya sabéis, si queréis jugar a las carreras de primos, procurad escoger un resto que no sea un cuadrado módulo el $q$ escogido.

Para probar, vamos a hacer carreras con las raíces digitales de los primos, que no son más que restos módulo 9, y comparar con el resultado teórico. Compitiendo en la pista, las raíces digitales 1, 2, 4, 5, 7 y 8, que son las coprimas con 9. Fijaos que 1, 4 y 7 son cuadrados módulo 9, y 2, 5 y 8 no. He tomado los tres primeros millones de primos menos el 2 y el 3. ¿En cuántas ocasiones cada una de las raíces digitales ha ido en cabeza de la carrera (posiblemente empatado con otra)? Aquí tenéis la tabla:

Como podéis ver, sobre 2.999.998 puntos de cronometraje, 1 y 4 solo han ido en cabeza 3306 y 7920 veces, aproximadamente un 0.1% y un 0.2% de las ocasiones. El 7 es más curioso, porque ha ido en cabeza un número de veces dos órdenes en magnitud mayor, pese a ser un cuadrado módulo 9. Las raíces 2, 5 y 8 han ido aproximadamente un tercio de las ocasiones en cabeza, 100.000 arriba, 100.000 abajo.

Vale, 1 y 4 no vale la pena que jueguen, no son de la misma liga que los otros. Voy a comparar los otros. Como el gráfico de la competición de los cuatro corredores de golpe es difícil de interpretar, he generado un gráfico para cada par de corredores. Muestro el primero y lo explico, y así el resto se entenderán.

Los puntos rojos repersentan el 2 y los azules el 5. En cada momento, el color que está en la línea superior es quien va ganando, y el de la línea inferior, perdiendo. Los puntos centrales son aquellos en los que empatan (que han quedado azules porque son los segundos que he dibujado, y se han superpuesto). El eje de abscisas representa el índice de los primos: va del tercero al que hace 3 millones.

Bueno, aquí vienen el resto de competiciones por parejas. De ellos podéis deducir fácilmente (módulo lo que podáis magnificar las imágenes y afinar las longitudes) en cada momento quién gana. Por ejemplo, en el primo que hace 2.000.000, 5 gana a 2, 2 gana a 7, 8 gana a 2 y 5 gana a 8, por tanto 5 gana.

Ah, bueno, una última cosa. ¿Cómo quedan al llegar al primo 3.000.000? Pues en primer lugar llega el 8, seguido del 7, seguido del 2, seguido del 4 casi empatado con el 5 y, farolillo rojo el 1. La diferencia entre el número de ochos y el número de unos al terminar la carrera es de 229. La mayor diferencia entre el que va en cabeza y el que va a la cola se da alrededor del primo número 2.271.290, es de 403, y en ese momento el que va ganando es el 8 y el que va perdiendo el 7.

Y hala, esta entrada participa en la edición 7.4 del Carnaval de Matemáticas, cuyo blog anfitrión es ::ZTFNews.

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

May 13, 2016CescLeave a comment

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 #CarnaMat74, así que mejor dejo algo para entonces. Continuará…)

Ramanujan en los cómics

April 26, 2016CescLeave a comment

Para recordar el aniversario de la muerte del mágico Srinivasa Ramanujan, tal día como hoy en 1920, ni os voy a hablar del taxi 1729 ni os voy a explicar ninguna de sus fórmulas, sino que, mientras espero que se dignen a distribuir en España su biopic, que ya han estrenado en Gran Bretaña (en tamil original, subtitulado en inglés… no hay esperanza, nunca la veremos por aquí), os voy a hablar de sus dos apariciones en cómics.

Ramanujan (o, más bien, sus manuscritos) es el protagonista de una aventura del buon vechio zio Martin Mystere, uno de los personajes emblemáticos de la editorial Bonelli y mi favorito. En el episodio 230 de sus aventuras (publicado en Italia en mayo de 2001 y en España en julio de 2006 por Aleta Ediciones), titulado precisamente, “La fórmula de Ramanujan” vemos en las primeras páginas a un Ramanujan en los últimos días de su vida descubriendo una fórmula que permite modificar la realidad y pidiendo a su esposa que destruya sus manuscritos.

Naturalmente, no lo hará, terminarán en malas manos y 80 años después tendrá que venir Martin Mystere a salvar el día. No os cuento más. Bueno, sí, las reflexiones finales de MM con las que suele cerrar cada episodio:

“Me pregunto si para entender en su totalidad la matemática de Ramanujan no fuese necesario variar el funcionamiento del propio cerebro, con efectos devastadores para el propio físico… Eso explicaría la misteriosa enfermedad de Ramanujan […] Genios como Ramanujan son únicos. Pasará mucho antes de que otro llegue a comprender la matemática del universo.”

Si os gusta Indiana Jones, tenéis que leer a Martin Mystere.

El otro cómic del que quería hablar es una biografía al estilo de las “Vidas ejemplares” de Novaro de mi niñez, tanto en intención como en estética. Publicada en la India por la editorial Amar Chitra Katha en 2012, en inglés, es una biografía convencional y clásica, poniendo énfasis en su genialidad y en lo mal que lo pasó en Inglaterra. Fue una de las primeras biografías de personalidades “contemporáneas” publicadas por esta editorial de cómics. No tiene mucho interés, más allá de lo exótico de ser un cómic indio. Y lo siento, ni lo tengo en digital ni puedo abrirlo para escanearlo, la encuadernación es un poco… débil.

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

April 24, 2016April 24, 2016CescLeave a comment

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-n 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-n 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:

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.
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.
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-n con n múltiplo impar de 3, pero tiene toda la pinta (va, conjetura).

¿Y los números Le Monde-959-n 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

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?

March 29, 2016March 29, 2016CescLeave a comment

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

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.

Lo confieso, yo también he caído en la tentación…

March 27, 2016Cesc2 Comments

Supongo que la mayoría de los lectores de blogs sobre matemáticas ya os habréis enterado de la “anomalía” en la distribución de la última cifra de los números primos detectada por K. Soundararajan y R. L. Oliver (en la foto, copiada del artículo en Quanta Magazine que ha popularizado el resultado) y publicada en el arXiv hace unos 15 días. En todo caso, aquí viene un resumen rápido de la anomalía en cuestión, por si hay algún despistado.

PrimesResearchers

Salvo el 2, que es el único primo que termina en cifra par (cualquier otro número par forzosamente es compuesto), y el 5, que es el único primo que termina en 5 (cualquier otro múltiplo de 5 forzosamente es compuesto), el resto de los números primos terminan en 1, 3 7 o 9, y resulta que se reparten esta última cifra de manera uniforme: salvo el 2 y el 5, si tomamos todos los números primos hasta una cierta cantidad n grande, aproximadamente un 25% terminarán en 1, un 25% en 3, un 25% en 7 y un 25% en 9. Las diferencias en los porcentajes son pequeñas (es el llamado sesgo de Chebyshev) y tienden a 0 a medida que n tiende a infinito.

Pues bien, Soundararajan y Oliver han observado que la frecuencia con la que un número primo termina en la misma cifra que el número primo que le precede es mucho menor que la de cualquier otra de las tres cifras posibles (excluyo el 2 y el 5): aproximadamente sólo un 18% de los pares de primos consecutivos terminan en la misma cifra, en vez del (aproximadamente) 25% que se esperaría si las últimas cifras se distribuyeran de manera realmente uniforme. En todo caso, la desviación detectada respecto del 25% es mucho mayor que la de Chebyshev. En el artículo mencionado los autores no sólo publican las cifras relativas a esta anomalía para los primeros 100 millones de primos, sino que además la demuestran suponiendo verdadera una conjetura de Hardy y Littlewood.

En un artículo de E. Lamb en Nature sobre el tema, Soundararajan dice que “Todas las personas a quienes se lo hemos explicado terminan escribiendo sus propios programas de ordenador para comprobarlo por ellas mismas”. Pues sí, yo también lo he hecho, con R y para 10 millones de primos. Y coincido con A. Granville (citado en el artículo en Quanta): encuentro asombroso que nadie se hubiera dado cuenta antes.

Como, además, tenía que realizar un pequeño vídeo en Jing para un curso sobre videotutoriales de la UIB, he aprovechado para matar dos pájaros de un tiro y grabar el experimento. Por desgracia, cuando ya estaba hecho he descubierto que no se pueda incluir un vídeo Jing en un blog WordPress de WordPress.com, así que si os interesa el vídeo, clicad en El vídeo del experimento. Y aprended de la experiencia: si queréis grabar un vídeo e incluirlo en un post, no uséis Jing y Screencast; colgadlo, por ejemplo, en Youtube.

En todo caso, os resumo el resultado del experimento numérico: a partir de un vector formado por los primeros 10 millones de primos (quitando los tres primeros y el último por razones técnicas obvias), obtengo la tabla siguiente, donde cada fila nos da la frecuencia relativa con la que, en mi vector, si un primo termina en la cifra de la fila, el siguiente primo termina en la cifra de la columna. Como podéis ver, en cada fila la probabilidad de que el siguiente primo repita la misma última cifra es mucho más baja que cualquiera de las otras tres. Por ejemplo, si un primo termina en 1, el siguiente termina en 1 un 18% de las veces, en 3 un 30% de las veces, en 7 otro 30% de las veces, y en 9 un 21% de las veces.

El codigo usado (salvo en la primera línea) es el siguiente:

 
primos=scan("https://dl.dropboxusercontent.com/u/72911936/primers10m.txt")
primos[1:100]
primos=primos[-(1:3)]
primos[1:100]
f=function(x){x%%10}
prim.uc=f(primos)
prim.uc[1:100]
round(prop.table(table(prim.uc)),4)
prim2=prim.uc[-1]
prim1=prim.uc[-length(prim.uc)]
t=table(prim1,prim2)
round(prop.table(t,margin=1),4)

Con la primera instrucción, se carga el fichero de los 10 millones de primos a partir de una copia que he dejado en mi dropbox. Para poderla ejecutar necesitáis una versión 3 y pico de R, y va a tardar un rato, porque son 93 Mb. Igual os conviene directamente guardar el fichero en vuestro directorio de trabajo y cargarlo con

 primos=scan("primers10m.txt")

o generar vuestra propia lista de primos con vuestro programa favorito.

Y como llego a tiempo, pues nada, esta entrada también participa en la Edición 7.2 del Carnaval de Matemáticas que alberga La Aventura de la Ciencia.

Poussy tiene un problema

March 24, 2016CescLeave a comment

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)

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.