Stack Exchange
Diophantine reciprocals III find output?
Diophantine reciprocals III
In the following equation x, y, and n are positive integers.
1/x  + 1/y = 1/n
For a limit L we define F(L) as the number of solutions which satisfy x < y ≤ L.
We can verify that F(15) = 4 and F(1000) = 1069.
Find F(10^12).


The equation is equivalent to z = xy/(x + y). Let d = gcd(x, y). Then
x = dm, y = dn, with gcd(m, n) = 1.
It follows that gcd(mn, m + n) = 1 so that
z = dmn / (m + n),
which implies (m + n) | d, i.e., d = k(m + n), k a positive integer.
Thus we obtain the solutions:
x = km(m + n), y = kn(m + n), z = kmn,
where the three parameters k, m, n are positive integers.


For I/p=15 I am getting o/p=4 & for I/p=1000 I am getting o/p=1069 in 18sec but for I/p=10^12 no o/p is being displayed. How to handle such huge I/p?​
public class testClient {

    public static void main(String[] args) {
        System.out.println(diophantineReciprocals(1000.0));
    }

    private static double diophantineReciprocals(double L) {
        double noOfSolutions = 0;
        double d = 1;
        double m = 1;
        double n = 1;
        double z = 0;

        for (double x = 1; x < L; x++) {
            for (double y = x + 1; y <= L; y++) {
                d = gcd(x, y);
                m = x / d;
                n = y / d;
                x = d * m;
                y = d * n;
                z = m * n * d / (m + n);

                if (/* z == (x * y) / (x + y) && */Math.round(z) != 0
                        && (z - Math.round(z)) == 0) {
                    noOfSolutions++;
                }
            }
        }

        return noOfSolutions;
    }

    private static double gcd(double x, double y) {
        double gcd = 1;
        for (double i = 2; i <= x; i++) {
            if (x % i == 0 && y % i == 0) {
                if (i > gcd) {
                    gcd = i;
                }
            }
        }
        return gcd;
    }

}


R.I.P Formation, 2014.

When you are only getting no output and the programm is still running,the only way to handle this is to write a better(faster) algorithm or buy better hardware.

i am looking for better (super fast ) algorithm . Any suggestions will help me ??

In one place you say 10^12, and in another 1012. They are kind of different. Which is it?

You should think amount how you can optimise your algorithm, e.g. for every solution x = km(m + n), y = kn(m + n), z = kmn you can use arbitrary values for k to get other solutions. You might thus only have to check for cases where n and/or m are primes (just an idea).

Also, use BigInteger, not double. Double is much slower, and you might run into precision issues.

Guntram Blohm : Thanks

Any solution based on exhaustive search will fail, as it will run in time O(L^2), totally unthinkable for L=10^12. Maybe you can use the kmn representation and loop on these variables instead (after you found a way to avoid duplicate solutions). Or use results from number theory.

I need to say again, first, improve your gcd, with x = 10^12, its time complexity will be O(n), with Euclidean algorithm, it will be O(logn)

This is http://projecteuler.net/problem=454, and Project Euler problems are almost never solvable with "brute force". As of now, only 112 people have solved that problem since it was published on January 11 (and unfortunately, I am not one of them :-(  )

@Martin R: You did a nice try .. thanks for ur help :)
