MarioYC's blog

SGU 330 — Numbers
By MarioYC, 13 years ago, In English

Link

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?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean 2 divisors? e.g. A = 1, B = 5

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply