Introducción

En este desafío, trataremos con un cierto gráfico infinito no dirigido, que yo llamo el gráfico de alto divisor . Sus nodos son los enteros a partir de 2. Hay un borde entre dos nodos a <b si a divide b y a ² ≥ b . El subgrafo formado por el rango de 2 a 18 se ve así:

16-8 12 18
  \|/ |/|
   4  6 9 10 15 14
   |  |/   |/   |
   2  3    5    7  11 13 17

Se puede demostrar que el gráfico infinito de divisores altos está conectado, por lo que podemos preguntar sobre la ruta más corta entre dos nodos.

Entrada y salida

Sus entradas son dos enteros a y b . Puede suponer que 2 ≤ a ≤ b <1000 . Su salida es la longitud del camino más corto entre una y b en el gráfico de alta divisor infinito. Esto significa el número de bordes en la ruta.

Puede encontrar útil el siguiente hecho: siempre existe una ruta óptima desde a hasta b que primero aumenta y luego disminuye, y solo visita nodos que son estrictamente menores que 2b ² . En particular, dado que b <1000 solo necesita considerar nodos inferiores a 2 000 000.

Ejemplos

Considere las entradas 3y 32. Una posible ruta entre los nodos 3 y 32 es

3 -- 6 -- 12 -- 96 -- 32

Esta ruta tiene cuatro bordes, y resulta que no hay rutas más cortas, por lo que la salida correcta es 4.

Como otro ejemplo, una ruta óptima para 2y 25es

2 -- 4 -- 8 -- 40 -- 200 -- 25

entonces la salida correcta es 5. En este caso, ninguna ruta óptima contiene el nodo 50 = lcm(2, 25).

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten. No hay límites de tiempo o memoria, por lo que se permite el forzamiento bruto.

Casos de prueba

2 2 -> 0
2 3 -> 4
2 4 -> 1
2 5 -> 5
3 5 -> 4
6 8 -> 2
8 16 -> 1
12 16 -> 2
16 16 -> 0
2 25 -> 5
3 32 -> 4
2 256 -> 3
60 77 -> 3
56 155 -> 3
339 540 -> 2
6 966 -> 4
7 966 -> 2
11 966 -> 4
2 997 -> 7
991 997 -> 4

Matlab, 218 190 175 bytes

function f(a,b);q=a;l(b)=0;l(a)=1;while~l(b);x=q(1);q=q(2:end);l(end+1:x^2)=0;g=x+1:x^2;s=2:x-1;u=[g(~mod(g,x)),s(~mod(x,s)&s.^2>=x)];u=u(~l(u));q=[q,u];l(u)=l(x)+1;end;l(b)-1

¡Gracias @beaker por el acceso directo en el paso de alargamiento de la lista!

Esta es una implementación dijkstra relativamente sencilla:

q=a;                  %queue
l(b)=0;       %list of path lengths
l(a)=1;
while~l(b);         %if there is no predecessor to b
    x=q(1);         %get first queue element
    q=q(2:end);
    %add edges 
    l(end+1:x^2)=0;% lengthen predecessor list if too short
    g=x+1:x^2;      % g=greater neighbours
    s=2:x-1;        % s=smaller neighbours %keep only valid/unvisited neighbours 
    u=[g(~mod(g,x)),s(~mod(x,s)&s.^2>=x)]; %-1byte
    u=u(~l(u));
    q=[q,u];      %add only hte valid nodes edges to queue
    l(u)=l(x)+1;       %mark x as predecessor  
end;
l(b)-1 %output length to the end of the path

_{^{sin convolución hoy}}

JavaScript (ES6), 186 bytes

(m,n)=>(g=i=>{for(q=[i],r=[],r[i]=j=0;i=q[j++];)for(k=i+i;k<=i*i&(k<m*m*2|k<n*n*2);k+=i)r[k]-r[i]<2?0:r[q.push(k),k]=r[i]+1},g(m),s=r,g(n),Math.min(...r.map((i,j)=>i+s[j]).filter(i=>i)))

Utiliza una función auxiliar gpara calcular todas las rutas ascendentes desde my nhasta el límite proporcionado, luego suma las rutas juntas y devuelve el valor más bajo.

Mathematica 98 bytes

Supongo que la función incorporada FindShortestPathno viola la restricción sobre las lagunas estándar. Si es así, házmelo saber y eliminaré este envío.

Fuerza bruta, por lo tanto lenta con grandes valores de b . Todavía estoy pensando en formas de acelerarlo.

h@{a_,b_}:=Length@FindShortestPath[Graph[Apply[Join,Thread[#<->Range[2,#] #]&/@Range[b^2]]],a,b]-1

Esto configura un gráfico con bordes apropiados entre los nodos de aa b^2. FindShortestPathencuentra la ruta más corta en el gráfico. Lengthcuenta los nodos;Length -1es el número de aristas

Thread[# <-> Range[2, #] #] &produce los bordes del gráfico completo. Por ejemplo, Thread[# <-> Range[2, #] #]&[5]produciría los bordes {5 <-> 2*5, 5 <-> 3*5, 5 <-> 4*5, 5 <-> 5*5}, es decir, {5 <-> 10, 5 <-> 15, 5 <-> 20, 5 <-> 25}.

Matlab (195) (185) (181) (179)(173)

Nota: Yo, el usuario Agawa001 personalmente, atestiguo que me gané al usuario @flawr haciendo uso de su asistencia.

 function t(a,b,p),for r=0:1,d=(b*~r+r*a)/gcd(a,b);while(d>1)p=p+1;e=find(~rem(d,1:d));f=max(e(a^(1-r/2)>=e));a=a*min([find(1:a*a>=b) a])^~(f-1);d=d/f;a=a*f^(1-2*r);end,end,p

• Esta función es diferente de otras, sigue un montón de cálculos matemáticos puros y factorizaciones, pero no tiene nada que ver con rutas o gráficos.

• Ejemplo de llamada de función:

   t(2,3,0)
  
   p =
  
   4
  

  Todos los casos de prueba están satisfechos

• Explicación:

Antes de comenzar con explicaciones, demostremos algunos lemas "no verdes":

Lema (1):(a,b) existe una ruta óptima entre dos números cualquiera de manera que los nodos aumenten primero y luego disminuyan.

Por qué ? Esto se demuestra simplemente porque la cantidad entera máxima que divide cualquier número aes, respectivamente, grande como el número en así mismo, por lo que, como un enfoque inteligente, debemos elegir multiplicar alo más posible para hacerlo lo suficientemente grande, y luego dividirlo por valores más grandes. Si alguna vez hacemos la vuelta, el número se areduce, por lo que necesitamos innecesariamente más iteraciones para multiplicarlo gradualmente de lo que se nos prescinde.

Lema (2): de un número aa b, si gcd(a,b)=1 ase multiplica por b, si bes más grande de alo que se multiplicará por un número conocido c, si se gcd>1 adebe multiplicar gradualmente por el mayor divisor de b/gcdnombre dque verifica la condición a >= dtambién cuando todo des mínimo son mayores que a, arecibe de a*cnuevo.

Esta suposición es simple para demostrar que cualquier nodo de inicio adebe multiplicarse hasta que alcance el múltiplo más pequeño de ay, bpor lo tanto, multiplicamos por proporciones de b*gcdinicio por el máximo que verifica la condición principal, que garantiza siempre el camino más corto a smp antes de que comience el proceso de división, o cuando dno está disponible, cse multiplica un número por apara hacer una condición válida a>=dpara esta primera etapa.

Lema (3): de un múltiplo gráfico-ultimum de aa b, el mcd de este número y bes en bsí mismo

Bueno, esto es solo una consecuencia de las manipulaciones anteriores, y los últimos pasos restantes también se realizan dividiendo gradualmente entre el divisor más grande que no excede su raíz cuadrada.

Dilema: ¿Cuál es el número óptimo cque se multiplicará iterativamente por aeso que conduciría directamente a la condición de apertura para la etapa 1 y luego el ultimum?

Buena pregunta, para cualquier situación simple hay una parada simple, por lo que suponiendo un ejemplo de dos fines (a,b)=(4,26)factorizados así:

  2 | 2
  2 | 13

Aparte del gcd=2número entero más pequeño por el que debe multiplicarse 2para alcanzar 13es 7, pero obviamente se descarta, porque es mayor que 2, por lo que a es cuadrado.

  2 | 2 
  5 | 13

Appearenlty en el segundo ejemplo (a,b)=(10,26)anterior cse mide como el número entero más bajo de 1a 5que excede 13/5por lo tanto satisface la condición del gráfico de desincrustación, que es 3, por lo que el siguiente paso aquí está multiplicando por3

  2 | 2 
  5 | 13
  3 |

Por qué ? Esto se debe a que, una vez que tenemos que multiplicar por 2*13/gcd=13para que coincida con el segundo lado de la tabla, la cantidad de basura que agregamos antes es óptimamente menor, y el movimiento a lo largo del gráfico se minimiza, si alguna vez multiplicamos por un valor mayor, como 10la posibilidad de dividir por el menor tiempo se reduce, y se habría incrementado en 1 otro paso divisorio para alcanzar nuestra meta 2*13. que se enumeran a: 13*2*5*10/2*5entonces 13*2*5/5. Mientras que, obviamente, aquí el número que se dividirá es5*3<13*2

y una cosa más ........ HAIL MATHS ...

Estos son mis resultados comparativos con los de @flawr. Solo preste atención a que hice un límite superior para el algoritmo de flawr de conserjería de ejecución de tiempo, ¡lleva demasiado tiempo!

Puede insertar los rangos de exploración inicial y final como variables ayb en el encabezado del código compilable en línea.