# Difference between revisions of "Project Euler/57"

### From charlesreid1

(→Solution Technique) |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||

Line 65: | Line 65: | ||

</pre> | </pre> | ||

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

==Flags== | ==Flags== | ||

{{ProjectEulerFlag}} | {{ProjectEulerFlag}} |

## Latest revision as of 03:48, 9 October 2019

## 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

Project Euler
Problem 1
Problem 11
Problem 51
Problem 100
Problem 500
- = in progress
· Template:ProjectEulerFlag · e |