Project Euler/57
From charlesreid1
Problem Statement
Continued fractions problem - this problem asks about the continued fraction representation of . 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:
For , we have
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
Flags