Project Euler Problem #57

Read the details of the problem here

Summary

Investigate the expansion of the continued fraction for the square root of two.

Solution

This looked like it was going to be a complicated question requiring some sort of recursive function but it ended up actually being quite simple. The key was spotting the (in retrospect somewhat obvious) pattern in the changes to the numerator and denominator in each expansion, which is why Euler puts so much stress on it in the question I suppose!

num_n / denom_n = num_n-1 + 2 * denom_n-1 / num_n-1 + denom_n-1

This then leads to a very simple and easy to code iterative solution. The use of BigInteger prevents overflow and makes it easy to compare the lengths.

def ( num, denom, answer ) = [ 3G, 2G, 0 ]

1000.times {
    ( num, denom ) = [ num + 2 * denom, num + denom ]
    if (num.toString().length() > denom.toString().length()) answer++
}

Run time is 0.13 seconds. Performance was quite adequate. Nothing much else to say on this as it’s very straightforward.

Conclusion

Not really a very Groovy solution, but the transparent integration Groovy has with BigInteger made it very easy to put this together without all the noise that you get in Java when using them.

Advertisement