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
Entradas
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.
ResponderEliminarHe utilizado 2 algoritmos distintos, el primero con 2 variantes.
ResponderEliminar-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.
Esto se mira muy interesante.
ResponderEliminarEjercicios de algebra
Ejercicios de aritmetica
Las cadenas más largas tienen longitud 77. He aquí una de ellas:
ResponderEliminar76-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 .