Carreras de raíces digitales de primos

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:

tablaRD

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.

2contra5

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.

2contra7

2contra8

5contra7

5contra8

7contra8

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

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á…)

 

Ramanujan en los cómics

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.

MMRamanujan

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.

2016-04-26 20.26.22

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.”

2016-04-26 20.38.32

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

Srinivasa_Ramanujan_5.1453448046

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)

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.

 

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

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.

 

2016-03-27 21.31.27

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

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.

Dos de cada tres estudiantes de la UIB, matriculados en carreras con muchos estudiantes. ¿Notición?

Estos días estoy meditando sobre aplicaciones de la paradoja de la amistad en el análisis de redes de interacciones de proteínas. Como Clara Grima ya explicó coj…mente esta paradoja en esta entrada de Cienciaxplora, voy a ahorraros los detalles. En todo caso, y en resumen, se trata del hecho que, para la mayoría de nosotros, nuestros amigos tienen, de media, más amigos que nosotros (y son más felices y más guapos que nosotros, y han ligado a lo largo de su vida más que nosotros y …). Por suerte, esto (normalmente) no tiene nada que ver con nuestra personalidad, sino que es un teorema de teoría de grafos atribuido a Scott Feld, que lo enunció, demostró y analizó en su artículo del 1991 titulado Why your friends have more friends than You do.

En realidad, esta paradoja viene de más lejos, de la llamada “paradoja del tamaño de la clase” que introdujeron el mismo Scott Feld y Bernard Grofman en un artículo de 1977 titulado Variation in class size, the class size paradox, and some consequences for students:

si escogemos al azar un estudiante de un centro, el tamaño esperado del curso en el que está matriculado es casi siempre estrictamente mayor que el tamaño medio de los cursos de su centro, y en todo caso nunca menor.

Además, en muchas distribuciones razonables de números de matriculados por curso, una gran mayoría de los estudiantes están matriculados en cursos más numerosos que la media (lo que les lleva, por comparación, al desánimo y al abandono de los estudios, según los autores; igual se lo podemos explicar a las comisiones de acreditación de los grados: “no es culpa nuestra que abandonen los estudios, es que no saben teoría de grafos y creen que son unos desgraciados por estar en cursos numerosos”).

Aquí viene la demostración. Sean x_1,\ldots, x_n los números de alumnos de los n cursos que ofrece un determinado centro. Entonces:

  • El valor medio de alumnos por curso es \overline{x}=(\sum_{i=1}^n x_i)/n
  • Pero si consultamos todos los estudiantes uno a uno y les pedimos cuántos estudiantes hay en su curso, y calculamos la media de los valores obtenidos, será otro cantar: para cada curso de x_i alumnos, habrá  x_i alumnos que contestarán “x_i”, por lo que cada respuesta  x_i aparecerá x_i veces. La suma total de respuestas será, por lo tanto, \overbrace{x_1+\cdots+x_1}^{x_1} +\cdots+ \overbrace{x_n+\cdots+x_n}^{x_n}=\sum_{i=1}^n x_i^2. La respuesta media por alumno (es decir, el número medio de matriculados en el curso en el que está matriculado un alumno escogido al azar), llamémosle \overline{x}_{al}, se obtendrá dividiendo esta suma por el número de respuestas:  \overline{x}_{al}=(\sum_{i=1}^n x_i^2)/(\sum_{i=1}^n x_i)

Si ahora restamos \overline{x}_{al}-\overline{x}=(\sum_{i=1}^n x_i^2)/(\sum_{i=1}^n x_i)-(\sum_{i=1}^n x_i)/n, un pequeño cálculo algebraico muestra que es igual a la varianza \mathrm{var}(x) de x_1,\ldots, x_n partido por su media \overline{x}. Y ahora es el momento de recordar que la varianza siempre es positiva, y es 0 sólo cuando x_1=\cdots=x_n. Por lo tanto, salvo en este caso, el número medio de matriculados en el curso de un estudiante escogido al azar será siempre mayor que el número medio de matriculados por curso. Y cuánto mayor sea la varianza, es decir, cuánto más variados sean los números x_1,\ldots, x_n, mayor será el cociente entre estas dos medias.

Vale, un experimento. He sacado de aquí los números de matriculados en los 30 grados de la UIB en el curso 2013-14 (los matriculados en dobles titulaciones los he contado en cada una de los grados involucrados). Estos números van de los 1228 matriculados en Administración de Empresas a los 93 matriculados en Matemáticas. He calculado el número medio de estudiantes por grado, \overline{x}, y el número medio de estudiantes matriculados en el grado de un estudiante aleatorio, \overline{x}_{al}. Los resultados (redondeados) han sido \overline{x}=366\overline{x}_{al}=593: un estudiante está matriculado de media en un grado de 593 estudiantes, pero el número medio de estudiantes por grado es de 366. Además, un 66.5% de los estudiantes de la UIB están matriculados en grados con un número de estudiantes mayor que la media. Es raro que algunos periódicos tradicionalmente críticos por defecto con la UIB no lo hayan publicado nunca.

El código R, por si queréis confirmar los números, es muy sencillo.

 ests.UIB=c(1228,1042,1028,623,612,560,497,467,432,412,400,351,339,
252,243,231,228,226,215,180,174,154,169,156,146,140,134,131,116,93)
#Media de alumnos por grado
mean(ests.UIB)
#Media de alumnos por grado desde el punto de vista del alumno
sum(ests.UIB^2)/sum(ests.UIB)
#Porcentaje de alumnos en grados más numerosos que la media
sum(ests.UIB[ests.UIB>mean(ests.UIB)])/sum(ests.UIB)

En cambio no sé cómo usar la paradoja de la amistad para explicar la percepción de los estudiantes de que sus amigos siempre tienen menos tareas que ellos para hacer en casa.

 

El 26 y los capicúas

Qué mejor día para quitar las telarañas a este blog que el 26 de febrero, 262, capicúa.
Aunque en realidad yo quería hablar de otro 26-2 capicúa, el 26^2=676. Resulta que el 26 es el menor número natural no capicúa que elevado al cuadrado da capicúa. El siguiente ya es el 264, que elevado al cuadrado da 69696.

Los números capicúas son muy populares en matemática recreativa, y recientemente se ha demostrado que también son relevantes en aritmética. Justo este pasado mes de agosto, William Banks, de la Univ. de Missouri, demostró que todo número natural es igual a la suma de números capicúas. Me podríais decir: bah, el 1 es capicúa y todo número es suma de unos, mira tú. No es esto. Bueno, sí, tendríais razón, pero Banks demostró algo más concreto: que, por grande que sea el número natural que nos den, siempre podemos encontrar una familia de, como máximo, 49 números capicúas cuya suma sea el número dado.

Hay muchas preguntas sobre potencias capicúas para las que los matemáticos desconocemos la respuesta. Por ejemplo, cuántos números no capicúas hay cuyo cuadrado sea capicúa? Hay infinitos? No se sabe. El más grande que se conoce tiene 28 dígitos, y su cuadrado, 55, y fue descubierto en 2008 por Feng Yuan, un informático aficionado a este tipo de cuestiones del estado de Washington, pero no sabemos si hay otros más adelante.

En cambio, es fácil producir tantos números capicúas con cuadrado capicúa como queráis: por ejemplo, tomad cualquier número formado por un 1, seguido de una secuencia de ceros y acabado con otro 1: 11, 101, 1001, 10001 etc. El cuadrado de un número de estos se obtiene siempre concatenando dos copias del número y cambiando el 11 que aparece en medio por un 2; es un buen ejercicio demostrarlo. Y en particular, como vemos, este cuadrado es capicúa.

Hay otras preguntas sobre números capicúas que permanecen abiertas. Por ejemplo, sólo se conoce un número no capicúa que elevado al cubo dé capicúa, el 2201; no se sabe si hay más. No se conoce ningún número no capicúa que elevado a la cuarta potencia dé capicúa, y no se sabe si existen. Y, para rematarlo, no se conoce ningún número diferente de 1, capicúa o no, tanto da, ninguno, que elevado a 5 o más dé capicúa. Antes de que os pongáis con la calculadora a buscar, tengo que avisaros de que ya se han comprobado todos los números de hasta 14 cifras y todas las potencias hasta 10. Será el tipo de problemas para los que decía Erdös que la matemática actual aún no está preparada?

Esta entrada participa en la Edición 7.1 del Carnaval de Matemáticas cuyo anfitrión es Tito Eliatron Dixit.

Añadido en prensa: Al poco de publicar la entrada me entero por Gaussianos de que  Javier Cilleruelo, de la Universidad Autónoma de Madrid, ha reducido la cota de Banks de 49 a 3: todo número natural es suma de como máximo 3 capicúas.