Todo entero positivo es suma de tres capicúas (por Javier Cilleruelo)

Todo el que haya visitado este blog con cierta frecuencia durante los últimos años conocerá a Javier Cilleruelo, ya que su nombre ha aparecido por aquí en varias ocasiones. Para quien no lo conozca, Javier Cilleruelo es Profesor Titular del Departamento de Matemáticas de la Universidad Autónoma de Madrid y miembro del Instituto de Ciencias Matemáticas (ICMAT), y ha colaborado en Gaussianos con varios artículos.

Javier CillerueloLa cosa comenzó con el problema de los conjuntos generalizados de Sidon (de cuya demostración hablé aquí), que resolvió junto a Imre Ruzsa y Carlos Vinuesa, y del cual nos habló Javier en este artículo. Más adelante, Javier siguió colaborando con Gaussianos con este artículo sobre el teorema de Szemerédi y con este artículo sobre la conjetura débil de Goldbach.

En esta ocasión, Javier nos habla sobre el último resultado que ha conseguido demostrar, junto a Florian Luca en este caso. El título de esta entrada lo dice todo: Javier y Florian han demostrado que todo entero positivo es suma de tres capicúas. Y además no solamente han dado una demostración, sino que dicha demostración es constructiva. Es decir, dado un numero entero positivo nos proporcionan un algoritmo para encontrar esos tres números capicúas. En lo que sigue os dejo el texto que me ha enviado Javier explicando dicho resultado y dando unas ideas de la demostración. Al final del mismo podéis encontrar un enlace al artículo técnico completo.


Un problema clásico en la teoría de los números consiste en estimar el número de sumandos necesarios para representar cualquier entero positivo como suma enteros de una sucesión notable de números, como los cuadrados, los primos, etc. Algunos ejemplos son los siguientes:

Todos estos resultados son óptimos en el sentido de que no son ciertos con menos sumandos. Hace unos días, en un trabajo con Florian Luca, hemos añadido un resultado a esta lista de resultados óptimos:

Teorema (J. Cilleruelo, F. Luca 2016): Todo entero positivo es suma de tres capicúas en cualquier base g \geq 5.

Los números capicúas, también llamados palíndromos, son aquellos que se leen igual de izquierda a derecha y de derecha a izquierda. El carácter capicúa de un número depende, claro está, de la base en la que escribamos dicho número. Así, por ejemplo, el número 11 es un número capicúa en base g=10, pero no lo es en base g=2 ya que en esta base se escribe de la forma 1011. El cero se considera un número capicúa (si no deberíamos cambiar el enunciado del teorema diciendo que todo entero positivo es suma de, a lo más, tres números capicúas).

El teorema es óptimo ya que no es difícil construir infinitos enteros que no son suma de dos capicúas.

La conjetura de que tres números capicúas (en base 10) eran suficientes para representar todos los enteros positivos era una conjetura que llevaba tiempo rondando en el área, pero sólo se había logrado demostrar que todo entero positivo era suma de 49 números capicúas (W. Banks, 2015).

Nuestra demostración es algorítmica; es decir, dado cualquier entero positivo, proporcionamos un algoritmo para hallar tres capicúas cuya suma sea dicho número. Por ejemplo, para el entero positivo que viene dado por los primeros 21 dígitos del número \pi,

314159265358979323846

los tres capicúas que nos da el algoritmo son los siguientes:

\begin{matrix} p_1=210100100101001001012 \\ \\ p_2=98639929400492993689 \\ \\ p_3=5419235847485329145 \end{matrix}

Eso no quiere decir que ésta sea la única representación de nuestro número como suma de tres capicúas. Por regla general, cada entero positivo tendrá muchas representaciones, pero para la demostración del teorema es suficiente con proporcionar una representación para cada uno de ellos. A continuación se exponen las ideas centrales del algoritmo.

El algoritmo

El algoritmo que utilizamos es complejo pero elemental, en el sentido que no se utilizan matemáticas profundas. Vamos a ilustrar nuestrol algoritmo viendo paso a paso cómo hemos llegado a los tres capicúas del ejemplo.

La configuración de partida es importante y depende del último y de los tres primeros dígitos del número que queremos representar. En nuestro algoritmo contemplamos hasta 13 configuraciones de partida. Para el entero de nuestro ejemplo la configuración de partida es la siguiente (en el artículo técnico están los detalles que justifican la elección de estos números para comenzar con el algoritmo):

Vamos a ir completando los dígitos de los tres capicúas desde la derecha y desde la izquierda simultáneamente. Con los dígitos de p_2 ajustamos los dígitos de la izquierda, y con los dígitos de p_3 ajustamos los dígitos de la derecha. Los dígitos de p_1, que salvo el inicial son 0 o 1, sirven para controlar las “llevadas” en las columnas de la izquierda (pondremos un 0 si hay llevadas y un 1 si no las hay). La estrategia es suponer que siempre vamos a tener una llevada cuando completamos los dígitos por la izquierda. Siendo así, el siguiente dígito de p_1 tiene que ser un 1 y el siguiente dígito de p_2 un 8:

Seguidamente completamos con un 4 para ajustar el dígito de la segunda columna por la derecha:

Como necesariamente vamos a tener una llevada en la cuarta columna por la izquierda (porque 4 es mayor o igual que 1), el siguiente dígito de p_1 va a ser un 0. Si no fuera a haber llevada pondríamos un 1 para suplir a la llevada que no tenemos. Como ya hemos comentado, los dígitos del primer capicúa sirven para controlar las llevadas: si la hay ponemos un 0 y si no la hay ponemos un 1.

El siguiente dígito de p_2 es 6 (para ajustar esa columna de la izquierda suponiendo que habrá llevada):

De nuevo completamos con un 1 para ajustar el dígito de la tercera columna por la derecha:

Seguimos con el algoritmo hasta que colisionan la parte izquierda con la parte derecha:

Siguiendo el algoritmo hemos logrado ajustar todos los dígitos excepto el de la columna central (obtenemos un 4 cuando deberíamos obtener un 5). Eso se debe a que no tenemos llevada de la columna anterior. Cuando eso sucede hay que hacer un ajuste, que en este caso es sencillo: simplemente cambiamos el dígito central de p_1 por un 1:

Con este último paso finaliza el algoritmo.


Invito a los lectores a que prueben a escribir su número favorito como suma de tres capicúas utilizando este algoritmo. Lo más seguro es que les ocurra como en este caso, que al final tengan que hacer algún ajuste en los dígitos centrales para que todo cuadre. Y en algunos casos estos ajustes no son nada sencillos. De hecho, el ejemplo que hemos elegido era de los más simples. Si el número de cifras es par el ajuste final se complica. Y si además el primer dígito de nuestro número es 1 y el siguiente 0,1 o 2, el ajuste se complica todavía más. Además, el algoritmo descrito funciona cuando nuestro número tiene 7 dígitos o más. Si tiene menos de 7 dígitos hay que aplicar otro algoritmo distinto que también está explicado en el artículo.

Las ideas centrales del algoritmo son las que se han descrito con el ejemplo, pero la casuística es tan compleja que hace que el artículo se alargue hasta las 39 páginas. EL lector interesado puede consultarlo en el siguiente enlace: Every positive integer is a sum of three palindromes.

Tanto las configuraciones de partida como los ajustes finales hacen que el algoritmo no funcione bien para las bases g \leq 4.

Terminamos esta entrada planteando algunos problemas:

  1. ¿Hay una proporción positiva de enteros que son suma de dos capicúas?
  2. ¿Cuantos capicúas en base 2 se necesitan para representar todos los enteros positivos?

Este último problema, que nosotros ya no hemos querido intentar, seguro que es accesible y puede ser interesante para algún estudiante aventajado que quiera dar sus primeros pasos en el mundo de la investigación. Se trataría de utilizar un algoritmo parecido (quizás sea incluso más sencillo) pero adaptado a la base 2.

También sería interesante para los expertos en programación implementar el algoritmo descrito en nuestro artículo. Desde Gaussianos animamos a quienes estéis interesados en ello a que lo hagáis y lo compartáis con nosotros.


Este artículo participa en la Edición 7.1 del Carnaval de Matemáticas, que en esta ocasión organiza Tito Eliatron.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

10 Comentarios

  1. me interesó el asunto y lo intentaré programar como ya hice en el caso de la suma de cuadrados para los enteros positivos! Claro el tema es que una vez que se encuentra el algoritmo hay que optimizarlo para que su respuesta sea rápida (salvo tener una super computadora), en el caso de la suma de cuadrados si el numero es muy muy grande puede ser lento, en eso estoy, o sino ocurre que el resultado no es el óptimo; es decir da más sumandos de los que bastarían!

    Publica una respuesta
  2. ¿Proporción positiva de enteros que son suma de dos capicúas? ¿Proporción positiva? No sé a qué se refiere… ¿A que haya al menos uno que pueda expresarse así?

    ¡Ah! Y por supuesto, enhorabuena a Javier Cilleruelo. Que siga cosechando resultados y éxitos.

    Publica una respuesta
    • Proporción quiere decir “densidad”. La proporción de los pares (y de los impares) es 1/2, la proporción de los múltiplos de 10 es 1/10. La proporción de las potencias de 2 es cero, en el sentido de que el límite de la proporción entre las potencias de 2 menores que n y n es cero cuando n tiende a infinito.

      Publica una respuesta
  3. Ante todo, enhorabuena a Javier y Florián.

    Para programar esto sería necesario primero saber exactamente como elegir los primeros dígitos y cómo hacer el ajuste central en todos los casos posibles.

    En base 2, todos los números capicúas son impares salvo el 0.

    Entonces, si el número que pretendemos conseguir es par, es obligatorio un número par de capicúas (a menos que uno de ellos sea 0).

    De la misma forma, si el número que pretendemos conseguir es impar, hará falta un número impar de capicúas diferentes de cero.

    Así que ahí ya tenemos una diferencia importante que invita a pensar que el algoritmo, de existir, tiene que ser esencialmente diferente.

    Publica una respuesta
  4. Bueno, desde que vi publicado este artículo en Facebook me interesó mucho y aún más la tarea pendiente de programar. Lamentablemente sólo tengo hecho un curso de Programación en Python de unos meses en la Facultad de Ingeniería de mi país (Uruguay), así que lo que he obtenido hasta el momento no implementa en absoluto el algoritmo constructivo de la demostración del teorema en cuestión pero sin dudas, creo que funciona aunque se podría optimizar mucho más por algún experto en la materia (pude pobrarlo sin problemas con enteros hasta el 1000 aunque demorando un poco en mi MacBook Air Standard de 4 Gb de Memoria). Bueno, aquí les dejo lo que logré hasta el momento y sepan disculpar mis carencias en asuntos informáticos ya que no soy programador, sólo un Profesor de Matemática de Secundaria con interés en la programación:

    print
    print “este programa le indicara la lista de ternas de capicuas cuya suma es un entero positivo n dado”
    print
    print “ingrese un entero positivo n”
    print
    n=input(“n = “)
    # esta funcion convierte un entero “a” en una lista con las cifras del mismo
    def lista1(a):
    l=[a%10]
    while a/10!=0:
    a=a/10
    l=[a%10]+l
    return l
    # esta funcion simetriza la lista obtenida a partir de las cifras de un entero “b”
    def lista2(b):
    return [(lista1(b))[len(lista1(b))-i-1] for i in range(0,len(lista1(b)))]
    # esta funcion devuelve la lista de todos los capicuas menores o iguales a un entero “c”
    def cap(c):
    return [k for k in range(0,c+1) if lista1(k)==lista2(k)]
    # esta funcion devuelve la lista formada por todas las ternas de capicuas cuya suma es “d”
    def cilleruelo(d):
    return [(x,y,z) for x in cap(d) for y in cap(d) for z in cap(d) if x+y+z==d and x<=y and y<=z]
    print
    print "el numero", n, "puede expresarse como suma de cualquiera de las siguientes ternas de capicuas:", cilleruelo(n)
    print

    Publica una respuesta
    • Acabo de observar que los códigos de las definiciones de las funciones salieron sin la indentación respectiva las cuales serían por definicion y por línea:
      def 1: 1 ind en la 1ª línea, 1 ind en el while, 2 inds en la 3ª línea, 2 inds en la 4ª línea y 1 ind en el return
      def 2: 1 ind en el return
      def 3: 1 ind en el return
      def 4: 1 ind en el return
      Obviamente, que sin estas correcciones, el programa no correrá.

      Publica una respuesta
  5. No tengo muy claro que la densidad de la suma de dos palíndromos sea positiva:
    hay 8 sumas menores que 10 (1 no es suma de dos palíndromos)
    hay 90 sumas menores que 100 (10 o 21 no son sumas)
    hay 981 menores que 1000
    hay 7995 menores que 10000
    hay 90856 menores que 100000
    hay 732836 menores que 10^6
    hay 8859893 menores que 10^7
    hay 68725987 menores que 10^8
    hay 875757971 menores que 10^9

    Recuerdos a Cilleruelo, fui alumno suyo.

    Publica una respuesta
    • Sorry for replying in English, but I hope that’s o.k.

      The following is only for Base-10. If we assume the definition of http://oeis.org/A035137 (0 is considered as a palindrome), then the decade-wise percentages of numbers that cannot be expressed by less than 3 palindromes is growing.

      From To 3 Palindromes
      needed
      1 10 0
      10 100 8
      100 1000 1
      1000 10000 1979
      10000 100000 7042
      100000 1000000 257918
      1000000 10000000 871675
      10000000 100000000 30132082
      100000000 1000000000 92939102

      So the density of numbers expressible as a sum of two base-10 palindromes is decreasing for larger numbers. Can we estimate what the density would be for 100 or 101-digit numbers?

      Publica una respuesta

Trackbacks/Pingbacks

  1. El 26 y los capicúas | Blioquinfo - […] en prensa: Al poco de publicar la entrada me entero por Gaussianos que  Javier Cilleruelo, de la Universidad Autónoma de Madrid, ha…
  2. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Todo el que haya visitado este blog con cierta frecuencia durante los últimos años…
  3. Ha fallecido Javier Cilleruelo | Matemáticas y sus fronteras - […] Había resuelto problemas importantes, como el de los conjuntos de Sidón en colaboración con Carlos Vinuesa e Imre Ruzsa,…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *