Introdução

Neste desafio, trataremos de um certo gráfico infinito e não direcionado, que chamo de gráfico de alto divisor . Seus nós são os números inteiros a partir de 2. Existe uma aresta entre dois nós a <b se a divide b e a ² ≥ b . O subgráfico formado pelo intervalo de 2 a 18 tem a seguinte aparência:

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

Pode-se mostrar que o gráfico do divisor alto infinito está conectado, para que possamos perguntar sobre o caminho mais curto entre dois nós.

Entrada e saída

Suas entradas são dois inteiros a e b . Você pode assumir que 2 ≤ a ≤ b <1000 . A sua saída é o comprimento do caminho mais curto entre um e b no gráfico alta divisor infinito. Isso significa o número de arestas no caminho.

Você pode achar útil o seguinte fato: sempre existe um caminho ideal de a para b que primeiro aumenta e depois diminui, e apenas visita nós que são estritamente menores que 2b ² . Em particular, como b <1000, você precisa considerar apenas os nós inferiores a 2 000 000.

Exemplos

Considere as entradas 3e 32. Um caminho possível entre os nós 3 e 32 é

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

Esse caminho tem quatro arestas e, como não há caminhos mais curtos, a saída correta é 4.

Como outro exemplo, um caminho ideal para 2e 25é

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

então a saída correta é 5. Nesse caso, nenhum caminho ideal contém o nó 50 = lcm(2, 25).

Regras e pontuação

Você pode escrever um programa completo ou uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas. Não há tempo ou limites de memória, portanto, a força bruta é permitida.

Casos de teste

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

Obrigado @beaker pelo atalho na etapa de alongamento da lista!

Esta é uma implementação dijkstra relativamente direta:

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

_{^{nenhuma convolução hoje}}

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)))

Usa uma função auxiliar gpara calcular todos os caminhos ascendentes a partir de me naté o limite fornecido, soma os caminhos juntos e retorna o valor mais baixo.

Mathematica 98 bytes

Suponho que a função FindShortestPathinterna não viole a restrição sobre brechas padrão. Se isso acontecer, avise-me e eu excluirei este envio.

Força bruta, portanto lenta com grandes valores de b. Ainda estou pensando em maneiras de acelerar isso.

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

Isso configura um gráfico com arestas apropriadas entre os nós de aa b^2. FindShortestPathlocaliza o caminho mais curto no gráfico. Lengthconta os nós; Length -1é o número de arestas.

Thread[# <-> Range[2, #] #] &produz as arestas do gráfico completo. Por exemplo, Thread[# <-> Range[2, #] #]&[5]produziria as arestas {5 <-> 2*5, 5 <-> 3*5, 5 <-> 4*5, 5 <-> 5*5}, ou seja {5 <-> 10, 5 <-> 15, 5 <-> 20, 5 <-> 25},.

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

Nota: Eu, pessoalmente, o usuário Agawa001, atesto que conquistei o usuário @flawr usando sua assistência

 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

• Essa função é diferente de outras, segue vários cálculos e fatorações matemáticas puras, mas não tem nada a ver com caminhos ou gráficos.

• Exemplo de chamada de função:

   t(2,3,0)
  
   p =
  
   4
  

  Todos os casos de teste são satisfeitos

• Explicação:

Antes de começar com explicações, vamos provar alguns lemas "não verdes":

Lema (1): Existe um caminho ideal entre dois números, de (a,b)maneira que os nós aumentam primeiro e depois diminuem.

Por quê ? Isso é simplesmente provado porque a quantidade máxima máxima que divide qualquer número aé, respectivamente, grande como o apróprio número ; portanto, como uma abordagem inteligente, devemos escolher multiplicar ao máximo possível para torná-lo suficientemente maior, depois dividindo-o por valores maiores. Se alguma vez fizermos o caminho inverso, o número adiminuirá; portanto, precisamos desnecessariamente de mais iterações para multiplicá-lo gradualmente de que somos dispensados.

Lema (2): de um número apara b, se gcd(a,b)=1 amultiplicado por b, se bfor maior do aque será multiplicado por um número conhecido c, se gcd>1 adeve ser multiplicado gradualmente pelo maior divisor de b/gcdnomeado dque verifica a condição a >= dtambém quando todos dsão mínimo são maiores que a, arecebe a*cnovamente.

Essa suposição é simples para provar que qualquer nó inicial adeve ser multiplicado até atingir o menor múltiplo de ae, bportanto, multiplicamos por proporções de b*gcdinício pelo máximo que verifica a condição principal, que garante sempre o caminho mais curto para o smp antes do início do processo de divisão, ou quando dnão está disponível, um número cé multiplicado por apara criar uma condição válida a>=dpara este primeiro estágio.

Lema (3): De um múltiplo gráfico-ultimo de aaté b, o MDC desse número e bé bele próprio

Bem, isso é apenas uma consequência das manipulações anteriores, e os últimos passos restantes também são feitos gradualmente dividindo-se pelo maior divisor que não excede sua raiz quadrada.

Dilema: Qual é o número ideal ca ser multiplicado iterativamente aque levaria diretamente à condição de abertura do estágio 1 e depois ao ultimo?

Boa pergunta, para qualquer situação simples, há uma simples aparação, portanto, assumindo um exemplo de dois fins (a,b)=(4,26)fatorados como este:

  2 | 2
  2 | 13

Além do gcd=2menor número inteiro que deve ser multiplicado 2para alcançar , 13é 7, mas é obviamente descartado, porque é maior que 2, então a é ao quadrado.

  2 | 2 
  5 | 13

A aparência no segundo exemplo (a,b)=(10,26)acima cé medida como o número inteiro mais baixo a partir 1do 5qual excede, 13/5portanto, satisfaz a condição de escala de gráfico, ou seja 3, portanto, a próxima etapa aqui é multiplicada por3

  2 | 2 
  5 | 13
  3 |

Por quê ? isso ocorre porque, uma vez que precisamos multiplicar 2*13/gcd=13para corresponder ao segundo lado da tabela, a quantidade de lixo eletrônico que adicionamos antes é otimamente menor, e a movimentação ao longo do gráfico é minimizada, se é que multiplicamos por um valor maior, como 10a chance de dividir por o menor número de vezes reduzido e teria sido aumentado em mais 1 passo divisor para alcançar nossa meta 2*13. que são enumerados para: 13*2*5*10/2*5then 13*2*5/5. Embora, obviamente, aqui o número a ser dividido seja5*3<13*2

e mais uma coisa ........ MAIL MAHS ...

Estes são meus resultados comparativos com os do @flawr, apenas preste atenção que eu fiz um limite superior para a execução do tempo de acordo com o algoritmo do flawr, isso leva muito tempo!

Você pode inserir os intervalos de verificação inicial e final como variáveis ​​aeb no cabeçalho do código compilável online.