1

I have a homework assignment that asks of me to check, for any three numbers, a,b,c such that 0<=a,b,c<=10^16, if I can reach c by adding a and b to each other. The trick is, with every addition, their value changes, so if we add a to b, we would then have the numbers a and a+b, instead of a and b. Because of this, I realized it's not a simple linear equation.

In order for this to be possible, the target number c, must be able to be represented in the form:

c = xa + yb

Through some testing, I figured out that the values of x and y, can't be equal, nor can both of them be even, in order for me to be able to reach the number c. Keeping this in mind, along with some special cases involving a,b or c to be equal to zero.

Any ideas?

EDIT: It's not Euclid's Algorithm, it's not a diophantine equation, maybe I have mislead you with the statement that c = xa + yc. Even though they should satisfy this statement, it's not enough for the assignment at hand.

Take a=2, b=3, c=10 for example. In order to reach c, you would need to add a to b or b to a in the first step, and then in the second step you'd get either : a = 2, b = 5 or a = 5, b = 3, and if you keep doing this, you will never reach c. Euclid's algorithm will provide the output yes, but it's clear that you can't reach 10, by adding 2 and 3 to one another.

Improve this question
11
  • I do know that those 4 that give me wrong output, should be classified as "NO" whereas, my code classifies them like "YES". What 4? Commented Dec 19, 2014 at 21:08
  • 1
    Seems you are searching for the extended euclidean algorithm (en.wikipedia.org/wiki/Extended_Euclidean_algorithm) or the Chinese remainder theorem (en.wikipedia.org/wiki/Chinese_remainder_theorem) Commented Dec 19, 2014 at 21:12
  • @quant why CRT? this is just Extended Euclidean, right? Commented Dec 19, 2014 at 21:13
  • 3
    Why do you believe that x and y can't both be even? If c is even, I don't see a reason to eliminate that case, unless there's some other interesting feature of the original problem that you omitted. Commented Dec 19, 2014 at 21:29
  • 1
    @ajb Yeah there has to be another condition, I just can't seem to set my eyes on it. I was thinking about optimizing recursion, but this course doesn't cover hashing, so there has to be a solution without it. If I don't find a simpler way, I'll try a dynamic programming approach. Commented Dec 19, 2014 at 23:05

3 Answers 3

Reset to default
2

Note: To restate the problem, as I understand it: Suppose you're given nonnegative integers a, b, and c. Is it possible, by performing a sequence of zero or more operations a = a + b or b = b + a, to reach a point where a + b == c?

OK, after looking into this further, I think you can make a small change to the statement you made in your question:

In order for this to be possible, the target number c, must be able to be represented in the form:

c = xa + yb

where GCD(x,y) = 1.

(Also, x and y need to be nonnegative; I'm not sure if they may be 0 or not.)

Your original observation, that x may not equal y (unless they're both 1) and that x and y cannot both be even, are implied by the new condition GCD(x,y) = 1; so those observations were correct, but not strong enough.

If you use this in your program instead of the test you already have, it may make the tests pass. (I'm not guaranteeing anything.) For a faster algorithm, you can use Extended Euclid's Algorithm as suggested in the comments (and Henry's answer) to find one x0 and y0; but if GCD(x0,y0) ≠ 1, you'd have to try other possibilities x = x0 + nb, y = y0 - na, for some n (which may be negative).

I don't have a rigorous proof. Suppose we constructed the set S of all pairs (x,y) such that (1,1) is in S, and if (x,y) is in S then (x,x+y) and (x+y,y) are in S. It's obvious that (1,n) and (n,1) are in S for all n > 1. Then we can try to figure out, for some m and n > 1, how could the pair (m,n) get into S? If m < n, this is possible only if (m, n-m) was already in S. If m > n, it's possible only if (m-n, n) was already in S. Either way, when you keep subtracting the smaller number from the larger, what you get is essentially Euclid's algorithm, which means you'll hit a point where your pair is (g,g) where g = GCD(m,n); and that pair is in S only if g = 1. It appears to me that the possible values for x and y in the above equation for the target number c are exactly those which are in S. Still, this is partly based on intuition; more work would be needed to make it rigorous.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

That GCD(x,y)=1 fixed it!, only problem I have now is optimizing because I'm over the time limit for execution at one of them. Awesome job!!
0

If we forget for a moment that x and y should be positive, the equation c = xa + yb has either no or infinitely many solutions. When c is not a multiple of gcd(a,b) there is no solution.

Otherwise, calling gcd(a,b) = t use the extended euclidean algorithm to find d and e such that t = da + eb. One solution is then given by c = dc/t a + ec/t b.

It is clear that 0 = b/t a - a/t b so more solutions can be found by adding a multiple f of that to the equation:

c = (dc + fb)/t a + (ec - af)/t b

When we now reintroduce the restriction that x and y must be positive or zero, the question becomes to find values of f that make x = (dc + fb)/t and y = (ec - af)/t both positive or zero.

If dc < 0 try the smallest f that makes dc + fb >= 0 and see if ec - af is also >=0.

Otherwise try the largest f (a negative number) that makes ec - af >= 0 and check if dc + fb >= 0.

Improve this answer

Comments

0 
import java.util.*;
import java.math.BigInteger;

public class Main
{
    private static boolean result(long a, long b, long c)
    {
        long M=c%(a+b);
        return (M%b == 0) || (M%a == 0);
    }
}

Idea:c=xa+by, because either x or y is bigger we can write the latter equation in one of two forms: c=x(a+b)+(y-x)b, c=y(a+b)+(x-y)a depending on who is bigger, so by reducing c by a+b each time, c eventually becomes: c=(y-x)b or c=(x-y)b, so c%b or c%a will evaluate to 0.

Improve this answer

5 Comments

It looks like you've written a recursive function that computes c % (a + b). Then, once it's computed M = c % (a + b), it returns true if M is divisible by a or b. I don't think this is the right answer, and in any case it's not a good use of recursion, to put it mildly.
This only tells me if the linear equation has solutions. However, as stated in my problem description and explained in one of my comments, it's not enough to determine whether I can reach the number c, by adding a and b to each other.
@ajb it actually computes c/(a+b) and then M=c/(a+b) is tested. Anyway, why isn't it a good use of recursion ?
@user2980055 why it's not enough ?
If c >= a+b, then result calls itself with c-a-b, then c-2a-2b, then c-3a-3b, etc., until c is less than a + b. Of course a and b are the same in every recursive call. The result is that the last c equals the original c % (a + b). Try it yourself if you don't believe me. The reason it's not a good use of recursion is because you're using recursion to compute something you can compute with one expression.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.