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


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.

  • $\begingroup$ Must the divisor be of the original $A$ or the current $A$ ? $\endgroup$
    – Peter
    Sep 26 '17 at 16:33
  • $\begingroup$ So we can sum $A$ with divisors of $B$ to reach $B$? $\endgroup$ Sep 26 '17 at 16:36
  • $\begingroup$ @SamAnderson Consider Z=A in each step sum Z with one of the divisors Z expect 1 and Z to get B $\endgroup$ Sep 26 '17 at 16:37
  • 1
    $\begingroup$ @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. $\endgroup$
    – user480281
    Sep 26 '17 at 16:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – 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.

Then you have in your tree structure both the factors that you've tried, and the steps that you've tried. Then if you realize that it didn't work with this highest factor you backtrack to the latest factor that was marked okay, at the latest step that was marked okay. Then continue from there until you reach your sum.

This problem relies on information that we can't know in the present time, if I add a factor to the sum then I will most likely have different factors next time etc. I would conjecture that the running time for the optimal algorithm here is non-polynomial so a brute-force tactic with some sort of tree is probably in that case your best bet. It would still be rather quick for small numbers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.