Algorithm to find the 2 largest numbers smaller than 2 integers a and b, that are divisible by each other.

Question

So here’s the challenge. Given 2 integers named a and b:

// Find the 2 largest numbers, smaller than a and b, that are divisible by each other.

// input: a:102,b:53 // output: (102,51)

// input: a:7,b:4 // output: (6,3)

// input: a:3,b:2 // output: (2,2)

The catch is, I don’t want to brute force it. I think it comes out to O(n²).

Here’s the signature for the method:

static Tuple<int, int> Analyze(int a, int b)
{
    if (a % b == 0)
        return new Tuple<int, int>(a, b);
    else
        // Here’s where the algorithm kicks in
}

Here’s a sample implementation:

static Tuple<int, int> Analyze(int left, int right)
{
    if (left % right == 0)
        return new Tuple<int, int>(left, right);
    else
    {
        for (int i = left; i >= right; i--)
        {
            for (int j = right; j >= 0; j--)
                if (i % j == 0)
                    return new Tuple<int, int>(i, j);
                else
                    i--;
        }
    }

    return null;
}

Here’s the test client:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Analyze(102, 53));
        Console.WriteLine(Analyze(6, 4));
        Console.WriteLine(Analyze(3, 2));
    }
}

There are obviously problems with my implementation, but it’s not bad for starters. For instance when I use 106 and 54 for my arguments, had I not decremented the outter loop variable (i-- in the else block), I’d have found a match with 106 and 53. Instead I find a match a 104 and 52, which isn’t quite right but is relatively close to the desired result. However, my sample implementation is much faster than a brute forced approach because I’d never loop anymore than b times, making it O(b). Thoughts, inputs?

Answer 1

Have you looked at the Wolfram article on Greatest Common Divisor and with a little google-ing I found for you a nice java code that implements a good GCD algorithm that you can modify for your purposes here

Answer 2

I think this would work, and be pretty straightforward, if I'm not confused, it should find the largest sum(a,b):

static Tuple Analyze(int a, int b)
{
    if (a % b == 0)
        return new Tuple(a, b);
    else {
        // The algorithm starts here.
        // This is fairly easy to implement with tail recursion, but not optimal:
        // There are two cases to worry about:
        //   1) 'b' will never divide into 'a' evenly, but 'b-1' might.
        //   2) 'a' doesn't divide evenly by 'b', but 'a-1' might.
        if (a < b*2) return Analyze(a, b-1);
        else return Analyze(a-1, b);
    }
}

Finding the largest lexicographically is trivial. Just loop from b downto 1.

You'll be able to do better if you jump by more than one, obviously. Here's an example in python (assuming a>b, if it's not, swap them):

>>> def analyze(a, b):
...   if 0 == a%b: return (a,b)          # If b is a factor, return them.
...   if a < b*2: return analyze(a,a/2)  # If b can't factor, adjust 'b' to next.
...   return analyze(a-(a%b),b)          # Otherwise, adjust 'a' to next.
... 
>>> map(lambda p: analyze(*p), [(102, 53), (6, 4), (3,2)])
[(102, 51), (6, 3), (3, 1)]