## Project Euler Problem #57

### May 21, 2010

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.

January 29, 2012 at 02:01

[…] question immediately reminded me of Problem #57 which ended up being quite a simple solution though it sounded involved initially. I took a look at […]