introduction

Dans ce défi, nous aurons affaire à un certain graphe infini non orienté, que j'appelle le graphe à diviseur élevé . Ses nœuds sont les entiers à partir de 2. Il y a un bord entre deux nœuds a <b si a divise b et a ² ≥ b . Le sous-graphique formé par la plage de 2 à 18 ressemble à ceci:

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

Il peut être démontré que le graphe diviseur infini est connecté, nous pouvons donc nous interroger sur le chemin le plus court entre deux nœuds.

Entrée et sortie

Vos entrées sont deux entiers a et b . Vous pouvez supposer que 2 ≤ a ≤ b <1000 . Votre sortie est la longueur du chemin le plus court entre a et b dans le graphique de diviseur élevé infini. Cela signifie le nombre d'arêtes dans le chemin.

Vous pouvez trouver le fait suivant utile: il existe toujours un chemin optimal de a vers b qui augmente d'abord puis diminue, et ne visite que les nœuds strictement inférieurs à 2b ² . En particulier, puisque b <1000, il suffit de considérer les nœuds inférieurs à 2 000 000.

Exemples

Considérez les entrées 3et 32. Un chemin possible entre les nœuds 3 et 32 ​​est

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

Ce chemin a quatre bords, et il s'avère qu'il n'y a pas de chemins plus courts, donc la sortie correcte est 4.

Comme autre exemple, un chemin optimal pour 2et 25est

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

donc la sortie correcte est 5. Dans ce cas, aucun chemin optimal ne contient le nœud 50 = lcm(2, 25).

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas gagne et les failles standard sont interdites. Il n'y a pas de limite de temps ou de mémoire, le forçage brutal est donc autorisé.

Cas de test

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 octets

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

Merci @beaker pour le raccourci dans l'étape d'allongement de la liste!

Il s'agit d'une implémentation dijkstra relativement simple:

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

_{^{pas de convolution aujourd'hui}}

JavaScript (ES6), 186 octets

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

Utilise une fonction d'aide gpour calculer tous les chemins ascendants à partir de met nà son tour jusqu'à la limite fournie, puis additionne les chemins ensemble et renvoie la valeur la plus basse.

Mathematica 98 octets

Je suppose que la fonction intégrée FindShortestPathne viole pas la contrainte sur les failles standard. Si c'est le cas, faites le moi savoir et je supprimerai cette soumission.

Force brute, donc lente avec de grandes valeurs de b. Je pense toujours à des moyens d'accélérer.

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

Cela crée un graphique avec des arêtes appropriées entre les nœuds de aà b^2. FindShortestPathtrouve le chemin le plus court dans le graphique. Lengthcompte les nœuds; Length -1est le nombre d'arêtes.

Thread[# <-> Range[2, #] #] &produit les bords du graphique complet. Par exemple, Thread[# <-> Range[2, #] #]&[5]produirait les bords {5 <-> 2*5, 5 <-> 3*5, 5 <-> 4*5, 5 <-> 5*5}, c'est-à-dire {5 <-> 10, 5 <-> 15, 5 <-> 20, 5 <-> 25}.

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

Remarque: Moi l'utilisateur Agawa001 personnellement j'atteste avoir séduit l'utilisateur @flawr en utilisant son assistance

 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

• Cette fonction est différente des autres, elle suit un tas de calculs et de factorisations mathématiques pures mais n'a rien à voir avec des chemins ou des graphiques.

• Exemple d'appel de fonction:

   t(2,3,0)
  
   p =
  
   4
  

  Tous les cas de test sont satisfaits

• Explication:

Avant de commencer par des explications, prouvons quelques lemmes "non verts":

Lemme (1): Un chemin optimal entre deux nombres (a,b)existe d'une manière que les nœuds augmentent d'abord puis diminuent.

Pourquoi ? Cela est simplement prouvé parce que le nombre entier maximal qui divise n'importe quel nombre aest respectivement grand comme le nombre alui-même, donc comme une approche intelligente, nous devons choisir de multiplier aautant que possible pour le rendre suffisamment plus grand, puis en le divisant par des valeurs plus grandes. Si jamais nous faisons le chemin, le nombre adiminue, nous avons donc besoin inutilement de plus d'itérations pour le multiplier progressivement dont nous sommes dispensés.

Lemme (2): D'un nombre aà b, si gcd(a,b)=1 aest multiplié par b, si best plus grand aqu'il sera multiplié par un nombre connu c, s'il gcd>1 adoit être multiplié progressivement par le plus grand diviseur de b/gcdnommé dqui vérifie la condition a >= dégalement lorsque tout dest à savoir le minimum sont plus grands que a, areçoit à a*cnouveau.

Cette hypothèse est simple pour prouver que tout nœud de départ adoit être multiplié jusqu'à ce qu'il atteigne le plus petit multiple de aet bdonc soit nous multiplions par des proportions de b*gcddébut par le maximum qui vérifie la condition principale, ce qui garantit toujours le chemin le plus court vers smp avant le début du processus de division, ou lorsqu'il dn'est pas disponible, un nombre cest multiplié par apour créer une condition valide a>=dpour cette première étape.

Lemme (3): D'un multiple du graphique ultime de aà b, le pgcd de ce nombre best blui - même

Eh bien, ce n'est qu'une conséquence des manipulations précédentes, et les dernières étapes restantes sont également effectuées progressivement en divisant par le plus grand diviseur qui ne dépasse pas sa racine carrée.

Dilemme: Quel est le nombre optimal cà multiplier de manière itérative aqui mènerait directement à la condition d'ouverture pour l'étape 1 puis à l'ultimum?

Bonne question, pour toute situation simple, il y a une parade simple, donc en supposant un exemple de deux extrémités (a,b)=(4,26)factorisées comme ceci:

  2 | 2
  2 | 13

Mis à part le gcd=2plus petit entier qui doit être multiplié par 2pour atteindre 13is 7, mais il est évidemment exclu, car il est supérieur à 2, donc a est carré.

  2 | 2 
  5 | 13

Appearenlty dans le deuxième exemple (a,b)=(10,26)ci - dessus cest mesuré comme le nombre entier le plus bas 1de 5laquelle dépasse d' 13/5où il satisfait à la condition de mise à l' échelle graphe, qui est 3, de sorte que la prochaine étape est ici en multipliant par3

  2 | 2 
  5 | 13
  3 |

Pourquoi ? c'est parce que, une fois que nous devons multiplier par 2*13/gcd=13pour correspondre au deuxième côté du tableau, la quantité d'ordure que nous avons ajoutée avant est de façon optimale la plus petite, et le déplacement le long du graphique est minimisé, si jamais nous multiplions par une valeur plus grande comme 10la chance de diviser par le moins de temps se réduit, et il aurait été augmenté d'une autre étape de division pour atteindre notre objectif 2*13. qui sont énumérés à: 13*2*5*10/2*5alors 13*2*5/5. Alors, évidemment, ici, le nombre à diviser est5*3<13*2

et encore une chose ........ SALUT MATHS ...

Ce sont mes résultats comparatifs avec ceux de @flawr faites juste attention à ce que j'ai fait une limite supérieure pour l'exécution du temps en respectant l'algorithme de flawr, cela prend trop de temps!

Vous pouvez insérer les plages de balayage de début et de fin en tant que variables a et b dans l'en-tête du code compilable en ligne.