Evidentemente todos los números que tienen solo dos dígitos distintos tiene buenos vecinos.
Para tres dígitos distintos tenemos por ejemplo :
1021 (el menor posible y además primo)
Tiene buenos vecinos porque el 0 está al menos una vez al lado del 1 y del 2, y lo mismo ocurre para el 1 y el 2.
Para cuatro dígitos distintos:
10203123 (¿Es el menor?)
24123413 que es primo. (¿Es el menor?)
La idea entonces es encontrar para N dígitos distintos (N=4 a N=10), el menor número con buenos vecinos que además sea primo.
Si lo quieres compartir o guardar
Entradas
Una propiedad de estos números es la siguiente:
ResponderEliminarsi rotamos cíclicamente cada dígito desde 0 hasta n, el número resultante sigue siendo buen vecino. En el ejemplo de Claudio del 1021, rotando cada dígito desde 0 hasta 2 podemos obtener los siguientes:
1021
2102
0210
De esta propiedad se deduce que dada una solución cualquiera siempre podremos encontrar otra que comience por 1. Por lo que el 24123413 no es el menor porque podemos rotar cada dígito hacia atrás una posición obteniendo otro resultado válido, el 13412342.
Vicente iq.
Observaciones:
ResponderEliminar1) El enunciado NO indica que los N dígitos deben ser los primeros N dígitos sino sólo que haya N dígitos distintos.
2) En realidad este problema no es relativo a números, sino a sartas lineales de signos con cierta propiedad de posicionamiento entre ellos.
Al mezclar esto con los números y en especial con los números primos yo encuentro que para N=4, el menor primo es 10307137
Para N=5 creo que la sarta más corta es de 14 signos totales. Si esto es así, el primo menor es éste: 10210427047147.
ResponderEliminarCarlos se puede hacer con 11 signos.
EliminarABCADCEBDEA
Carlos se puede hacer con 11 signos.
EliminarABCADCEBDEA
Tienes razón. Lo cual quiere decir que mi técnica para producir una sarta de longitud mínima aún requiere refinamiento. Ahora bien usando tu sarta, el primo menor es este: 10213250351.
ResponderEliminarHe modificado mi técnica y parece que 11 es un mínimo real para N=5. Aunque yo obtengo esta sarta ABCADBECDEA, que es un poco distinta que la tuya dado que se giró la subsarta BEC. Sin embargo NO produce un primo menor que el ya obtenido con tu sarta. Estas rotaciones de subsartas están interesantes...
ResponderEliminarClaudio, mis mínimos para N 6 y 7 son 18 y 22. Qué opinas?
ResponderEliminarSi Carlos, no logro hacerlo con menos caracteres
Eliminar(N^2)/2 y N(N-1)/2+1 dan el largo de la sarta minima si N es par o impar, respectivamente.
EliminarCarlos, ¿es posible tener acceso a la demostración de esos resultados?
Eliminarvicente iq.
Estoy preparando un artículo. Pero más q una demostración de las fórmulas, lo q tengo es una ejemplificación de los resultados obtenidos mediante el algoritmo empleado (greddy o voraz) y que yo sugiero y supongo siempre genera solucion y que esa solución es mínima. Si todo eso es cierto, las formulas se obtienen por generalización de esos resultados, más bien que pir deducción. En un par de días publico o envio esto.
EliminarGracias. Otros resultados mas tarde.
ResponderEliminarInteresante el tema.
ResponderEliminarSe pueden plantear muchas variantes como por ejemplo utilizar sartas, como las llama Carlos, en forma de collar; o sea, el primer dígito unido con el último.
Se puede extender a 2 dimensiones para disponer en un cuadriculado los números de forma que se consideren vecinos los que estén al lado de un dígito dado en horizontal o vertical.
etc.
Vicente iq.
En atención a la solicitud de Vicente aquí va mi rollototote.
ResponderEliminarGeneración de sarta S mínima de N signos tal que cada uno de ellos tenga como vecino al menos una vez a
el resto de los signos (Entrada 1399, Claudio Meller)
A. El algoritmo general para generar S es el siguiente
1. Ordenar los N signos en un orden cualquiera Este orden se recorrerá ciclicamente hasta terminar.
2. Iniciar con el primero de los símbolos ordenados en el paso anterior.
3. Procediendo siempre en el mismo orden, elegir el primero de los signos restantes para formar un
apareamiento no existente.
4. Finalizar cuando se hayan obtenido todos los apareamientos posible. En casi contrario regresar a 3.
B. Comentarios al algoritmo
a) Una sarta S completa y mínima tiene una longitud total L. La cantidad total de apareamientos a
lograr es A=N(N-1)/2.
b) Al ir generando S, se dice que se produce un "cierre" en la sarta, cuando no se han obtenido todos
los apareamientos posibles, y sin embargo ninguna elección de nunguno de los signos restantes produce
un nuevo apareamiento.
c) Cuando N es impar, el único "cierre" de S se produce al final de la sarta y éste siempre ocurre al
colocar por (N+1)/2 vez el primer símbolo de la sarta. Todos los demás símbolos ocurren (N-1)/2 veces.
En este caso L = N(N-1)/2+1.
d) Cuando N es par, el primer cierre de S se produce cuando se han colocado L-N+2 signos quedando por
colocar N-2 signos distintos. Entre esos N-2 signos pendientes de colocar se encuentran los (N-2)/2
apareamientos restantes. Estos apareamientos pendientes simplemente se añaden a la sarta previamente
obtenida.Todos los símbolos ocurren N/2 veces. En este caso L = (N^2)/2.
C. Soluciones
Se usará el símbolo "|" para indicar la posición en el que ha ocurrido un "cierre" en la sarta
generada.
C1, Soluciones impares para N=3, 5, 7 y 9
N=3, L=4, A=3, A->C
S=ABCA|
N=5, L=11, N=10, A->E
S=ABCDEACEBDA|
N=7, L=22, N=21, A->G
S=ABCDEFGACEGBDFADGCFBEA|
N=9, L=37, A=36, A->I
S=ABCDEFGHIACEGIBDFHADGAEHBEICFBGCHDIFA|
C2, Soluciones pares para N=4, 6, 8 y 10
N=4, L=8, A=6, A->D
S=ABCDAC|BD|
N=6, L=18, A=15, A->F
S=ABCDEFACEADFBD|EB|CF|
N=8, L=32, A=28, A->H
S=ABCDEFGHACEGADFHBDGBEHCFAE|BF|CG|HD|
N=10, L=50, A=45, A->J
S=ABCDEFGHIJACEGIADFHJBDGJCFIBEHAEIGCAFJDHBF|GB|CH|ID|EJ|
D. Comentarios finales
D1. Sean A y P prefijos y sufijos válidos con respecto a S. A y P son válidos si estan compuestos
exclusivamente por símbolos pertenecientes a S. Si S es una solución, entonces AS, SP y ASP son
soluciones válidas también.
D2. Cualquier subsarta entre dos elementos iguales y consecutivos en una sarta, pueden rotarse 180° y
la sarta no se altera en cuanto a los apareamientos contenidos.
Muchas gracias Carlos,
Eliminarvicente iq.