¿Cuántas hojas tiene el árbol 2017?

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

 

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.

 

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.