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!

numn / denomn = numn-1 + 2 * denomn-1 / numn-1 + denomn-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.

Advertisements

One Response to “Project Euler Problem #57”


  1. […] 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 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: