I'm trying to understand when there is a solution (even though it may have more than 500 moves).
It can't always be done with one divisor, for example A = 4, B = 9 (4->6->9), but I think it can always be done with two divisors, a proof of this would be related somehow to Bezout's identity. Say we pick d1 divisor of A, and d2 divisor of B then we can find integers x,y such that
d1 * x + d2 * y = B - A
since the gcd of d1 and d2 divides B — A, the thing is that one of x and y could be negative. Is there a way to make both positive?
What do you mean 2 divisors? e.g. A = 1, B = 5
What I mean is we can add a first divisor d1 some number of times and then another divisor d2 until we get to B.
For example, for A = 4, B = 15, we can choose d1 = 2, d2 = 3, then the sequence would be: 4,4 + 2,6 + 3,9 + 3,15
I think it's a counterexample: A=437 B=493 However, it can be easily done using 3 numbers: the smallest divisor of A, the smallest divisor of B, and 2.