Cédric Villani tiene una sección en Le Monde donde propone acertijos matemáticos. En el primero, introduce los capicúas (números palíndromos) y luego hace dos preguntas:
Intentemos adivinar las respuestas con ayuda de Python.
import itertools
from __future__ import division
Una primera forma burda de generar la lista de capicúas de longitud $m$ es tomar la lista de todos los números de longitud $m$ (o sea aquellos que están entre $10^{m-1}$ y $10^{m}-1$) y filtrar los palíndromos. Este proceso, claro, es dispendioso y toma demasiado tiempo incluso para valores bajos de $m$.
La estrategia complementaria es construir los capicúas usando manipulación de cadenas. Para longitudes pares, basta generar cualquier número de la mitad de la longitud deseada y luego adjuntarlo revertido. Con los impares es similar. Eso es lo que hago a continuación:
def capicuas(m):
n = int(m/2) + m%2
p = itertools.product(range(10), repeat = n) # "producto cartesiano" de la lista range(10)
lista = [''.join(map(str,x)) for x in p]
if m%2 == 0:
t = [x+x[::-1] for x in lista] # Python-locura sintáctica: "Javier"[::-1] = "reivaJ"
else:
t = [x[:-1]+x[::-1] for x in lista]
capicuas = [int(x) for x in t if x[0] != '0']
if m==1: capicuas = [0] + capicuas # Para que entre los palíndromos de longitud 1 incluya el 0.
return sorted(capicuas) # El sorted sobra, creo, pero mejor me curo en salud.
Una prueba:
print capicuas(1)+ capicuas(2) + capicuas(3) + capicuas(4)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 555, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 666, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 777, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 888, 898, 909, 919, 929, 939, 949, 959, 969, 979, 989, 999, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 3003, 3113, 3223, 3333, 3443, 3553, 3663, 3773, 3883, 3993, 4004, 4114, 4224, 4334, 4444, 4554, 4664, 4774, 4884, 4994, 5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 6006, 6116, 6226, 6336, 6446, 6556, 6666, 6776, 6886, 6996, 7007, 7117, 7227, 7337, 7447, 7557, 7667, 7777, 7887, 7997, 8008, 8118, 8228, 8338, 8448, 8558, 8668, 8778, 8888, 8998, 9009, 9119, 9229, 9339, 9449, 9559, 9669, 9779, 9889, 9999]
Un cálculo combinatorio sencillo sería suficiente para obtener la respuesta, pero supongamos que no queremos pensar demasiado. Miremos, usando nuestra función, cuántos capicúas de longitud m hay para m entre 1 y 11 e intentemos conjeturar la respuesta general.
[len(capicuas(m+1)) for m in range(11)]
[10, 9, 90, 90, 900, 900, 9000, 9000, 90000, 90000, 900000]
Es decir, hay 10 capicúas de longitud 1, 9 de longitud 2, 90 de longitud 3, 90 de longitud 4...
Así, pareciera que el número de capicúas de longitud $m$ es $9\times 10^n$ para algún $n$ que tal vez depende de $m$. ¿Cuál es el $n$?
Para $m=2$ tenemos $n=0.$ Para $m=3$ tenemos $n=1.$ Para $m=4$ tenemos $n=1$ otra vez. Para $m=5$ tenemos $n=2,$ y así sucesivamente.
Pareciera que el valor de $n$ depende de si $m$ es par o impar:
Si estamos en lo correcto, el número de capicúas de longitud 12 sería $9\times 10^5 = 900000:$
len(capicuas(12))
900000
Así, nuestra conjetura para el número de capicúas de longitud 351 es $9\times 10^{(351-1)/2} = 10^{175}.$
El ejercicio obligatorio subsiguiente, por supuesto, es hacer el conteo explícito. Villani lo hace en su video de respuesta.
Definamos una función que calcule las diferencias entre elementos consecutivos de una lista:
def diferencias(l):
return [l[i+1]-l[i] for i in range(len(l)-1)]
Con esta función podemos hacer varios experimentos.
Por ejemplo, podemos calcular las posibles diferencias entre capicúas consecutivos de longitud $m=11$ en la lista ordenada que produce nuestra función generadora.
set(diferencias(capicuas(11)))
set([100000L, 11L, 1100L, 110L, 110000L, 11000L])
En este caso la mínima diferencia entre dos capicúas consecutivos de longitud $m=11$ es precisamente 11.
Calculemos la mínima diferencia para $m=1, 2, \ldots, 12:$
[min(diferencias(capicuas(i+1))) for i in range(12)]
[1, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11L, 11L]
La regularidad es clara. Nuestra conjetura aquí sería que la diferencia mínima entre dos capicúas de longitud $m$ es (casi) siempre igual a 11. Las únicas excepciones son $m=1$ y $m=3$.
¿Y cuáles son las parejas de capicúas que producen la diferencia mínima? Escribamos una función que las lista:
def minimas_diferencias(n):
print "Capicúas de longitud ", n
l = capicuas(n)
m = min(diferencias(l))
print "Mínima diferencia: ", m
print "Entre:"
b = l[0]
for i in l[1:]:
if i-b == m:
print b, i
b = i
Por probar, empecemos con el caso sencillo $m=2$:
minimas_diferencias(2)
Capicúas de longitud 2 Mínima diferencia: 11 Entre: 11 22 22 33 33 44 44 55 55 66 66 77 77 88 88 99
Ahora, por curiosidad, miremos la aberración $m=3$:
minimas_diferencias(3)
Capicúas de longitud 3 Mínima diferencia: 10 Entre: 101 111 111 121 121 131 131 141 141 151 151 161 161 171 171 181 181 191 202 212 212 222 222 232 232 242 242 252 252 262 262 272 272 282 282 292 303 313 313 323 323 333 333 343 343 353 353 363 363 373 373 383 383 393 404 414 414 424 424 434 434 444 444 454 454 464 464 474 474 484 484 494 505 515 515 525 525 535 535 545 545 555 555 565 565 575 575 585 585 595 606 616 616 626 626 636 636 646 646 656 656 666 666 676 676 686 686 696 707 717 717 727 727 737 737 747 747 757 757 767 767 777 777 787 787 797 808 818 818 828 828 838 838 848 848 858 858 868 868 878 878 888 888 898 909 919 919 929 929 939 939 949 949 959 959 969 969 979 979 989 989 999
¿Qué pasa de ahí en adelante? Calculemos desde $m=4$ hasta $m=12:$
for i in range(9):
minimas_diferencias(4+i)
Capicúas de longitud 4 Mínima diferencia: 11 Entre: 1991 2002 2992 3003 3993 4004 4994 5005 5995 6006 6996 7007 7997 8008 8998 9009 Capicúas de longitud 5 Mínima diferencia: 11 Entre: 19991 20002 29992 30003 39993 40004 49994 50005 59995 60006 69996 70007 79997 80008 89998 90009 Capicúas de longitud 6 Mínima diferencia: 11 Entre: 199991 200002 299992 300003 399993 400004 499994 500005 599995 600006 699996 700007 799997 800008 899998 900009 Capicúas de longitud 7 Mínima diferencia: 11 Entre: 1999991 2000002 2999992 3000003 3999993 4000004 4999994 5000005 5999995 6000006 6999996 7000007 7999997 8000008 8999998 9000009 Capicúas de longitud 8 Mínima diferencia: 11 Entre: 19999991 20000002 29999992 30000003 39999993 40000004 49999994 50000005 59999995 60000006 69999996 70000007 79999997 80000008 89999998 90000009 Capicúas de longitud 9 Mínima diferencia: 11 Entre: 199999991 200000002 299999992 300000003 399999993 400000004 499999994 500000005 599999995 600000006 699999996 700000007 799999997 800000008 899999998 900000009 Capicúas de longitud 10 Mínima diferencia: 11 Entre: 1999999991 2000000002 2999999992 3000000003 3999999993 4000000004 4999999994 5000000005 5999999995 6000000006 6999999996 7000000007 7999999997 8000000008 8999999998 9000000009 Capicúas de longitud 11 Mínima diferencia: 11 Entre: 19999999991 20000000002 29999999992 30000000003 39999999993 40000000004 49999999994 50000000005 59999999995 60000000006 69999999996 70000000007 79999999997 80000000008 89999999998 90000000009 Capicúas de longitud 12 Mínima diferencia: 11 Entre: 199999999991 200000000002 299999999992 300000000003 399999999993 400000000004 499999999994 500000000005 599999999995 600000000006 699999999996 700000000007 799999999997 800000000008 899999999998 900000000009
¿Notan el patrón? La diferencia mínima siempre se consigue entre las parejas de la forma A9999···9999A y B0000···0000B donde A es un dígito entre 1 y 8 y B=A+1.
Supongo que el ejercicio siguiente sería demostrar que no hay dos capicúas de longitud $m\geq 4$ cuya diferencia sea menos que 11.
Con lo ya construído es fácil seguir jugando. Por ejemplo, podemos buscar los capicúas con longitud menor a 12 tales que en representación binaria también son capicúas.
Para esto, escribamos una función que, dada una cadena, juzgue si es palíndromo o no:
def es_palindromo(x):
x = str(x)
if x == x[::-1]: return True
else: return False
Probémosla usando un palíndromo de Pedro Poitevín:
es_palindromo("Arriba la birra".lower().replace(' ', ''))
True
Ahora calculemos todos los capicúas (en base 10) de longitud menor que 12 que también son capicúas en su representación binaria:
caps = []
for i in range(12):
caps = caps + palindromos(i+1)
dobles_capicuas = [x for x in caps if es_palindromo(bin(x)[2:])]
for a in dobles_capicuas:
print a, "=", bin(a)[2:]
print "Total de capicúas dobles: ", len(dobles_capicuas)
0 = 0 1 = 1 3 = 11 5 = 101 7 = 111 9 = 1001 33 = 100001 99 = 1100011 313 = 100111001 585 = 1001001001 717 = 1011001101 7447 = 1110100010111 9009 = 10001100110001 15351 = 11101111110111 32223 = 111110111011111 39993 = 1001110000111001 53235 = 1100111111110011 53835 = 1101001001001011 73737 = 10010000000001001 585585 = 10001110111101110001 1758571 = 110101101010101101011 1934391 = 111011000010000110111 1979791 = 111100011010110001111 3129213 = 1011111011111101111101 5071705 = 10011010110001101011001 5259525 = 10100000100000100000101 5841485 = 10110010010001001001101 13500531 = 110011100000000001110011 719848917 = 101010111010000000010111010101 910373019 = 110110010000110011000010011011 939474939 = 110111111111110011111111111011 1290880921 = 1001100111100010100011110011001 7451111547 = 110111100000111101111000001111011 10050905001 = 1001010111000101001010001110101001 18462126481 = 10001001100011011011011000110010001 32479297423 = 11110001111111010101011111110001111 75015151057 = 1000101110111010000000101110111010001 110948849011 = 1100111010101000100010001010101110011 136525525631 = 1111111001001100011100011001001111111 Total de capicúas dobles: 39
(Este es otro cuaderno de Javier Moreno)