9
\$\begingroup\$

I have designed the code but the problem is it timeouts as the range is 1000000000 but works fine with 1000. Any idea to optimize this or a mathematic logic for it? I just need to find the no of pairs(a,b) such that a < b and a*b % a+b == 0 if a range is given, eg: 15 - o/p 4 as (3,6)(4,12)(6,12)(10,15).

php code:

$count = 0;
$no = 1000;
for($b = 1; $b <= $no; $b ++) {
    for($a = 1; $a < $b; $a ++) {
        $sum = $a + $b;
        $prod = ($a * $b);

        if (($prod % $sum == 0) {
            ++ $count;
        }
        $arr [$b] = $count;
    }
}

echo '<pre>';
print_r($arr);
echo '<pre>';

I need some math logic to get no of pairs rather performing actual process as above. If I found a relation or expression for this then actual process is not required.

\$\endgroup\$
0
7
\$\begingroup\$

These kind of puzzles have to be solved by first analyzing the problem. If you look at the samples that you have already found you will notice that in all samples the two numbers share a rather large common factor. This makes sense, since if a and b have a common factor then both a+b and a*b are divisible by this common factor, which increases the probability that a+b divides a*b. So let's try to find out more formally when (a,b) is a good pair:

Let g=gcd(a,b). Then there exist integers r,s with

a = r * g
b = s * g

Then

a + b = (r+s)*g
a * b = r*s*g^2

Thus a+b divides a*b if (r+s)*g divides r*s*g^2 and hence if r+s divides r*s*g. Also since g is the greatest common divisor it follows that r and s have no divisor in common (i.e. gcd(r,s)=1). From Euclid's algorithm follows that gcd(r+s,r) = 1 and gcd(r+s, s) = 1 and hence also gcd(r+s, r*s) = 1. Thus if r+s divides r*s*g then r+s must divide g.

Thus all the good pairs below a bound N can be described as follows: If r,s,k are integers such that 1 < r < s < N^0.5, gcd(r,s)=1 and s * (r + s) * k <= N then (a,b) = (r * (r + s) * k, s * (r + s) * k) is a good pair.

Implementing this isn't hard. Running the algorithm up to 10^9 takes a few minutes (depending on the programming language).

One big question remains: Why on earth has the problem been migrated to "Code review"?

\$\endgroup\$
2
  • \$\begingroup\$ +1 nice answer. I suspect that the phrase you used "increases the probability that" is more accurately worded "is a requirement for"; coded in my language of choice, I ran the algorithm up to n=40k and all of the solution pairs shared a common factor. \$\endgroup\$ – devgeezer May 12 '11 at 0:14
  • \$\begingroup\$ very gd algorithm \$\endgroup\$ – Angelin Nadar May 12 '11 at 9:07
3
\$\begingroup\$

I have no algorithm that gives you the number for a given number (and I doubt there is one), but I can see a little improvement: indeed, if both a and b are odd, a + b which is even cannot divide a * b which is odd, so a * b % a + b == 0 is wrong.

Here is a little implementation of this trick:

$count = 0;
$no = 1000;
$odd_b = True
for($b = 1; $b <= $no; $b ++) {
    if ($odd_b) {
        for($a = 2; $a < $b; $a += 2) {
            $sum = $a + $b;
            $prod = ($a * $b);

            if (($prod % $sum == 0) {
                ++ $count;
            }
            $arr [$b] = $count;
        }
    } else {
        for($a = 1; $a < $b; $a ++) {
            $sum = $a + $b;
            $prod = ($a * $b);

            if (($prod % $sum == 0) {
                ++ $count;
            }
            $arr [$b] = $count;
        }
    }
    $odd_b = ! $odd_b;
}

echo '<pre>';
print_r($arr);
echo '<pre>';

I used a boolean for performance (avoids to test for each value of b that b % 2 == 0). With this you should avoid around 1 case out of 4, so 25% improvement.

\$\endgroup\$
1
  • \$\begingroup\$ yes i agree too.I can add it.vote for 25% improvement. \$\endgroup\$ – Angelin Nadar May 9 '11 at 10:36

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.