Shortest paths in a divisor graph

Question

Introduction

In this challenge, we will be dealing with a certain infinite undirected graph, which I call the high divisor graph. Its nodes are the integers starting from 2. There is an edge between two nodes a < b if a divides b and a² ≥ b. The subgraph formed by the range from 2 to 18 looks like this:

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

It can be shown that the infinite high divisor graph is connected, so we can ask about the shortest path between two nodes.

Input and output

Your inputs are two integers a and b. You can assume that 2 ≤ a ≤ b < 1000. Your output is the length of the shortest path between a and b in the infinite high divisor graph. This means the number of edges in the path.

You may find the following fact useful: there always exists an optimal path from a to b that's first increasing and then decreasing, and only visits nodes that are strictly less than 2b². In particular, since b < 1000 you only need to consider nodes less than 2 000 000.

Examples

Consider the inputs 3 and 32. One possible path between the nodes 3 and 32 is

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

This path has four edges, and it turns out there are no shorter paths, so the correct output is 4.

As another example, an optimal path for 2 and 25 is

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

so the correct output is 5. In this case, no optimal path contains the node 50 = lcm(2, 25).

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time or memory limits, so brute forcing is allowed.

Test cases

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

Answer 1

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

Thanks @beaker for the shortcut in in the list lengthening step!

This is a relatively straightforward dijkstra implementation:

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

_{^{no convolution today}}

Answer 2

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

Uses a helper function g to calculate all the ascending paths from m and n in turn up to the provided limit, then sums the paths together and returns the lowest value.

Answer 3

Mathematica 98 bytes

I am assuming that the built-in function, FindShortestPath does not violate the constraint about standard loopholes. If it does, just let me know and I'll delete this submission.

Brute force, hence slow with large values of b. I'm still thinking of ways to speed it up.

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

This sets up a graph with appropriate edges between the nodes from a to b^2. FindShortestPathfinds the shortest path in the graph. Lengthcounts the nodes; Length -1 is the number of edges.

Thread[# <-> Range[2, #] #] & produces the edges of the full graph. For example, Thread[# <-> Range[2, #] #]&[5] would produce the edges {5 <-> 2*5, 5 <-> 3*5, 5 <-> 4*5, 5 <-> 5*5}, that is, {5 <-> 10, 5 <-> 15, 5 <-> 20, 5 <-> 25}.

Answer 4

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

Note: Me the user Agawa001 personally I attest that I won over the user @flawr making use of his 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

• This function is different drom others, it does follow a bunch of pure mathematical calculations and factorisations but has nothing to do with paths or graphs.

• Example of function call:

   t(2,3,0)
  
   p =
  
   4
  

  All test cases are satisfied

• Explanation:

Before beginning with explanations lets prove some lemmas "not green ones":

Lemma(1): An optimal path between any two numbers (a,b) exists in a way the nodes are firstly increasing then decreasing.

Why ? This is simply proven because the maximal integer amount that divides any number a is respectively big as the number a itself, so as a clever approach we must choose to multiply a as much as possible to make it sufficiently bigger, then dividing by bigger values. If ever we do the way round, the number a shrinks, so we need needlessly more iterations to multiply it gradually that we are dispensed with.

Lemma(2): From a number a to b, if gcd(a,b)=1 a is multiplied by b, if b is bigger than a it will be multiplied by a known number c, if gcd>1 a must be multiplied gradually by the biggest divisor of b/gcd named d that verifies the condition a >= d also when all d's namely the minimum are bigger than a, a receives a*c again.

This assumption is simple to prove any starting node a must be multiplied until it reaches the smallest multiple of a and b so either we multiply by proportions of b*gcd beginning by the maximum which verifies the main condition, that guarantees always the shortest path to smp before division process begins, or when d isnt available a number c is multiplied by a to make a valid condition a>=d for this first stage.

Lemma(3): From a graph-ultimum multiple of a to b, the gcd of this number and b is b itself

Well this is just a consequence of the previous manipulations, and the last remaining steps are also done gradually dividing by the biggest divisor which doesnt exceed its square root.

Dilemma: What is the optimum number c to be iteratively multiplied by a that would lead straight along to the opening condition for stage 1 then the ultimum?

Good question, for any simple situation there is a simple parry, so assuming an example of two ends (a,b)=(4,26) factorized like this:

  2 | 2
  2 | 13

Apart from the gcd=2 the smallest integer wich must be multiplied by 2 to reach 13 is 7, but it is obviously ruled out, cuz it is bigger than 2, so a is squared.

  2 | 2 
  5 | 13

Appearenlty in the second example (a,b)=(10,26) above c is measured as the lowest integer from 1 to 5 which exceeds 13/5 hence it satisfies the condition of graph-scaling, which is 3, so the next step here is multiplying by 3

  2 | 2 
  5 | 13
  3 |

Why ? this is because , once we have to multiply by 2*13/gcd=13 to match the second side of the table, the junk amount we added before is optimally smallest, and moving along the graph is minimized, if ever we multiplied by bigger value like 10 the chance of dividing by the least times reduces, and it would have been increased by 1 another dividing step to reach our goal 2*13. which are enumerated to: 13*2*5*10/2*5 then 13*2*5/5. Whilst, obviously here the number to be divided by is 5*3<13*2

and one more thing ........ HAIL MATHS...

---

These are my comparative results with @flawr 's ones just pay attention that i made an upper bound for time execution consering flawr's algorithm, it takes too much time!

You may insert the starting and ending scanning ranges as variables a and b in the header of online compilable code.