Cadena más larga de 100 números

Le he estado dando vueltas a un problema curioso en http://simplementenumeros.blogspot.com.es/2013/05/1130-los-numeros-del-1-al-100.html. Se trata de formar la cadena más larga posible con los números del 1 al 100, de forma que cada número en la cadena sea o bien múltiplo o bien divisor de sus vecinos.

Una solución es la siguiente cadena de 77 números:

76-38-19-95-5-85-17-34-68-4-92-46-23-69-3-87-29-58-2-62-31-93-1-77-11-99-33-66-22-44-88-8-96-32-64-16-48-24-72-36-18-54-27-81-9-63-21-42-84-28-56-14-98-49-7-35-70-10-80-40-20-100-50-25-75-15-45-90-30-60-12-6-78-39-13-26-52

En realidad hay muchas soluciones con 77 números; por ejemplo, en esta cadena se pueden intercambiar las posiciones de 26 y 52, y de 40 y 80.

La cadena tiene la siguiente estructura:

• 4 múltiplos de 19, y el 5;
• 4 múltiplos de 17, y el 4;
• 4 múltiplos de 23 y el 3;
• 3 múltiplos de 29 y el 2;
• 3 múltiplos de 31 y el 1;
• y finalmente una cadena de 54 números múltiplos de 2, 3, 5, 7, 11 y 13.

Es fácil ver que en la solución no deberían aparecer los primos mayores que 50; 53,59,61,67,71,73,79,83,89 y 97; porque sólo se pueden conectar al 1. Ni tampoco aquellos primos entre 33 y 50 junto con sus dobles, 37 y 74, 41 y 82, 43 y 86, 47 y 94; porque sólo se pueden conectar al 1 y al 2. En cambio, los múltiplos de 17, 19, 23, 29 y 31 sí pueden aparecer, porque son 5 grupos con más de tres números que sólo se pueden conectar al 1,2,3,4,5. Si en la solución apareciese por ejemplo el 37, sería porque alguno de estos primos no aparecería, y por tanto se podría alargar la solución quitando el 37 y poniendo el primo que no estaba.

Aparte de estos 18 números (primos > 50 y primos y dobles entre 33 y 50) que sabemos que no pueden aparecer, hay otros 5 que no aparecen en la solución dada: 51, 55, 57, 65 y 91. El 51 y 47 son múltiplos de 17 y 19 y podrían aparecer, pero entonces tendrían que desaparecer el 85 y el 95.

Así que en realidad sólo se podría mejorar la solución en 3 números. Pero esto no es posible. La cadena larga, a partir del 1, es la más larga posible (demostrado por ordenador). Es verdad que podríamos quitar, por ejemplo, los múltiplos de 31 para dejar libre el 1, con lo cual podríamos enganchar algún otro número. Pero es que en la solución ya hay tres múltiplos de 31; incluso si pudiésemos enganchar los tres números que nos faltan, perderíamos otros 3, con lo cual no mejoraríamos la longitud de la cadena.

Total, que queda por ver cómo encontrar la cadena larga. El problema se puede formalizar como buscar el camino más largo posible en un grafo de 57 vértices. Se podría usar backtracking a lo bruto, pero esto tarda demasiado.

Una primera mejora para podar el árbol es, antes de probar a explorar un nuevo vértice, contar el número de vértices en su componente conexa. Si la componente conexa tiene N vértices, la cadena que ya he explorado tiene longitud L, y de momento el récord de cadena más larga que he encontrado es R, entonces no tiene sentido explorar si N+L <= R, no se podrá batir el récord. Esto mejora una burrada el tiempo de búsqueda, pero sigue siendo lento.

La clave para conseguir explorar todo el árbol de caminos es darse cuenta de que los grafos que quedan por explorar son bastante "fibrosos". Al principio hay unos cuantos números muy conectados, pero tienen a desaparecer pronto y dejar un grafo deshilachado. Por ejemplo, uno que aparece relativamente pronto y que estuve depurando en detalle es éste:

Se entra por el 35. Aunque tiene 21 vértices, está claro que los dos caminos más largos posibles son de sólo 11. Una forma de afinar la cota sería darse cuenta de que en ese grafo hay 6 hojas (vértices con un único vecino) y como sólo podremos usar como mucho uno de ellos (porque ahí se acaba el camino), aunque el grafo tenga 21 vértices podemos acotar los vértices útiles a 21-6+1.

Pero claro, podemos repetir esta observación... en un grafo como éste, si primero quitamos las hojas 21,25,35, nos queda otro grafo con hojas, así que le quitamos 3 y 5 y finalmente nos queda un grafo con 1 vértice sin hojas (15 no es hoja porque está conectado al principio del camino). Así que en ese grafo el camino más largo que podremos recorrer es de 1+2 vértices (1 es el número de vértices en el grafo final y 2 es el número de veces que hemos eliminado hojas).

Acotando de esta forma la longitud del camino máximo dentro de un subgrafo, se puede explorar todo el grafo de 57 vértices en unas 24 horas.