# Sum a number with divisors to get another number

There are two numbers A and B, in each step we can sum A with one of its divisors expect 1 and A. We want to get from A to B, what is the minimum step that we can get B?

Note: Sometimes we can't get to B from A. If, say, $A,B$ are both primes then it is clear that we can not achieve this. In the cases where it is possible, I want an algorithm that solve this problem.

Edit: Consider Z=A in each step sum Z with one of the divisors Z expect 1 and Z to get B

$4≤A≤B≤100000$

Example: A=4, B=24

$$4\to 6\to 8\to 12\to 18\to 24$$

As you can see the answer is 5 for this example.

• Must the divisor be of the original $A$ or the current $A$ ? Sep 26 '17 at 16:33
• So we can sum $A$ with divisors of $B$ to reach $B$? Sep 26 '17 at 16:36
• @SamAnderson Consider Z=A in each step sum Z with one of the divisors Z expect 1 and Z to get B Sep 26 '17 at 16:37
• @lulu When viewed as a number theory problem this is not gibberish. Suppose that we have two non-primes that both have very large number of factors and they are not close in some well defined way. Then the question of the existence of this procedure can be raised. And the question of the number of steps as a function of $A$ and $B$ can be raised. This does not look trivial to me.
– user480281
Sep 26 '17 at 16:51
• Never apologize for that, my Farsi is a lot worse. Let me apologize instead for mistaking a translation for something else. I will take a look at the question with fresh eyes now.
– lulu
Sep 26 '17 at 17:12

This obviously doesn't work when $A$ or $B$ or both are prime, so that's an important addendum.
My first thought for an algorithm would be to create a tree of some kind, marking each step with an ordering that works (so you can backtrack easily) then using the $gcd(a,b)$ function to add the highest factor you can and checking whether that was okay and then marking that as well.