Project Euler/64

Problem Statement

More investigation of continued fractions and the continued fraction representation of square roots.

Link: https://projecteuler.net/problem=64

Blog post: Computing square roots using continued fractions: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/063/Problem063.java

Solution Technique

The blog post linked above contains some of the code used to solve this problem, but it basically boils down to implementing the recurrence relation formula that we already saw in Project Euler/57, with various initial conditions.

Continued fractions are implemented as a class. Key functionality includes:

• Check if integer is perfect square
• Solve the Pell equation
• Find the convergents P, Q of a continued fraction
• Find the (shorter than 10-long) continued fraction representation of an integer (uses normal float type)
• Find the (really long) continued fraction representation of an integer (uses arbitrary precision BigDecimal type)

$ \dfrac{P_n}{Q_n} = \dfrac{ a_n P_{n-1} + P_{n-2} }{ a_n Q_{n-1} + Q_{n-2} } $

Code

Link: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064

ContinuedFractionBig.java defines the ContinuedFractionBig class: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/ContinuedFractionBig.java

Problem064.java uses the ContinuedFractionBig class to solve the problem: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/064/Problem064.java