Capicúas

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:

  1. ¿Cuántos capicúas de 351 dígitos hay?
  2. ¿Cuál es la diferencia mínima entre dos capicúas de longitud 351?

Intentemos adivinar las respuestas con ayuda de Python.

In [171]:
import itertools
from __future__ import division 

Lista de capicúas de longitud m

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:

In [228]:
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:

In [229]:
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]

¿Cuántos capicúas de longitud m hay?

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.

In [180]:
[len(capicuas(m+1)) for m in range(11)]
Out[180]:
[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:

  • Cuando $m$ es par, $n=(m/2)-1.$
  • Cuando $m$ es impar, $n=(m-1)/2.$

Si estamos en lo correcto, el número de capicúas de longitud 12 sería $9\times 10^5 = 900000:$

In [181]:
len(capicuas(12))
Out[181]:
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.

¿Cuál es la diferencia mínima entre dos capicúas de longitud m?

Definamos una función que calcule las diferencias entre elementos consecutivos de una lista:

In [164]:
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.

In [182]:
set(diferencias(capicuas(11)))
Out[182]:
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:$

In [166]:
[min(diferencias(capicuas(i+1))) for i in range(12)] 
Out[166]:
[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:

In [224]:
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$:

In [227]:
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$:

In [220]:
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:$

In [221]:
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.

¿Capicúas simultáneamente en varias bases?

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:

In [200]:
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:

In [209]:
es_palindromo("Arriba la birra".lower().replace(' ', ''))
Out[209]:
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:

In [223]:
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:]
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

(Este es otro cuaderno de Javier Moreno)