jueves, 2 de mayo de 2013

1130 - Los números del 1 al 100

Nueve de los diez primeros números se pueden acomodar de la siguiente manera:

 8 - 4 - 2 - 6 - 3 - 9 - 1 - 5 - 10

De forma tal que cada número o es múltiplo o es divisor de sus vecinos. Yo no encontré forma de acomodar los diez primeros números.

La idea es lograr con esta regla formar la cadena mas larga posible con los números del 1 al 100 inclusive.
Yo tengo una solución de mas de 70  y menos de 80 números, pero seguramente ustedes mis queridos lectores podrán superarla.

¿Existe una regla que nos permita calcular cuál es el número máximo de términos que se pueden colocar cuando los números van del 1 a N?

Por ejemplo para 
N= 2,  1-2
N =3,  3-1-2
N =4,  3-1-2-4
N =5,  el cinco no se puede agregar, o si se agrega hay que sacar el tres
N =6,  5-1-3-6-2-4
etcétera.


Este problema había aparecido hace unos cuantos años en el excelente blog 3decas de merfat (lamentablemente ya no se actualiza), donde está mi solución  
Si lo quieres compartir o guardar
Share/Bookmark

4 comentarios:

  1. Una parte de la regla por la cual preguntas es esta: Se descartan todos los números primos mayores a N/2. Para el caso N=100 habría que descartar los primos 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, y a lo sumo podríamos añadir alguno de ellos si queda libre el número 1 para terminar la cadena con la secuencia "1-primo". Digamos que esto nos daría un tope de cadena máxima de 91 términos.

    ResponderEliminar
  2. He utilizado 2 algoritmos distintos, el primero con 2 variantes.
    -Leyendo los nºs en orden del 1 al 100 y añadiendo el que cumpla la condición, después de 1 hora de ejecución obtiene una cadena máximo de 45 nºs.
    -El mismo algoritmo pero leyendo los nºs del 100 al 1 obtiene en el mismo tiempo una cadena máxima de 65 nºs.
    -El otro algoritmo lo calculo ordenando los nºs por el nº de múltiplos y divisores que tiene cada nº. Cogiendo en primer lugar los nº que tienen menos divisores. En el mismo tiempo que el otro algoritmo encuentra una cadena máxima de 63 nºs.
    En ambos casos utilizo backtracking sin ningún tipo de poda.
    Si pruebo alguna otra forma os indicaré los resultados.

    vicente iq.

    ResponderEliminar
  3. Las cadenas más largas tienen longitud 77. He aquí una de ellas:

    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

    Cuento los detalles en https://jugandoaprogramar.blogspot.com.es/2018/01/cadena-mas-larga-de-100-numeros.html .

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!