Luís Ramalho bio photo

Luís Ramalho

Engineering, Product, Business & Management

Twitter LinkedIn Github Stackoverflow

Square root convergents is a problem in which one must find how many fractions of the square root of 2 contain a numerator with more digits than denominator.

Since we are dealing with big numbers, we should use BigIntegers. Then, I looked for a pattern since we are given the first 8 iterations.

Respectively: \(\frac{3}{2}\), \(\frac{7}{5}\), \(\frac{17}{12}\), \(\frac{41}{29}\), \(\frac{99}{70}\), \(\frac{239}{169}\), \(\frac{577}{408}\), \(\frac{1393}{985}\)

I found one that applied for both the numerator and denominator:

Afterwards, it was trivial to code the solution:

ArrayList<BigInteger> n = new ArrayList<>();
n.add(BigInteger.valueOf(3)); // first numerator
n.add(BigInteger.valueOf(7)); // second numerator

ArrayList<BigInteger> d = new ArrayList<>();
d.add(BigInteger.valueOf(2)); // first denominator
d.add(BigInteger.valueOf(5)); // second denominator

BigInteger two = BigInteger.valueOf(2);
for (int i = 1; i < 1000; i++) {
    n.add(n.get(i).multiply(two).add(n.get(i - 1)));
    d.add(d.get(i).multiply(two).add(d.get(i - 1)));
}

int count = 0;
for (int i = 0; i < n.size(); i++) {
    if (n.get(i).toString().length() > d.get(i).toString().length()) {
        count++;
    }
}

return count;

The full solution can be found here.