Project Euler/57

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.

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

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);
    	}
    }

Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/057/ContinuedFraction.java