Problem Statement

Continued fractions problem - this problem asks about the continued fraction representation of $\sqrt{2}$. In particular, we are to examine the first 1,000 continued fraction terms, determine what they are, and count how many times the numerator has more digits than the denominator.

Solution Technique

Also see blog post: Computing square roots using continued fractions: https://charlesreid1.github.io/computing-square-roots-part-2-using-continued-fractions.html

This utilizes a recurrence relation for the numerator and denominator, so we can start with the first few terms and obtain as many terms as we wish.

The recurrence relation is: $a_i = a_{i-1} + 2 b_{i-1}$ $b_i = a_{i-1} + b_{i-1}$

For $\sqrt{2}$, we have $a(1) = 3, b(1) = 2$

Code

import java.math.BigInteger;
/**
* Find the number of terms in the first 1,000 iterations
* of the continued fraction of sqrt(2) whose denominator
* has more digits than its numerator.
*
* This utilizes the recurrence relation for the nth iteration,
* a(1) = 3,  b(1) = 2
*
* a_i = a_{i-1} + 2 b_{i-1}
*
* b_i = a_{i-1} + b_{i-1}
*
* I actually implemented this in Excel, to begin with, just cuz,
* but these numbers get REALLY huge, REALLY fast.
*/
public class ContinuedFraction {
public static final BigInteger TWO = new BigInteger("2");
public static void main(String[] args) {
BigInteger aim1 = new BigInteger("3");
BigInteger bim1 = new BigInteger("2");
BigInteger ai, bi;

int nterms = 1000;
int noverflows = 0;
for(int i=0; i<nterms; i++) {
ai = aim1.add( bim1.multiply(TWO) );
bi = aim1.add( bim1 );
if( ai.toString().length() > bi.toString().length() ) {
noverflows++;
}
aim1 = ai;
bim1 = bi;
}
System.out.println(noverflows);
}
}