Project Euler Problem #57

Problem #57 is the first of several Project Euler problems to involve infinite continued fractions for irrational numbers, and it is the first of several problems that can b killed with Pell Equations. The problem reads:

Project Euler Problem 57: Square root convergents
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
 2–√=1+1/(2+1/(2+1/(2+…)))

By expanding this for the first four iterations, we get:
 1+1/2=3/2=1.5
 1+1/(2+1/2)=7/5=1.4
 1+1/(2+1/(2+1/2))=17/12=1.41666…
 1+1/(2+1/(2+1/(2+1/2)))=41/29=1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than the denominator?

As it turns out, the process of determining the continued fraction approximations for a square root is closely related to the problem of solving a Pell Equation. Here’s my solution:

Solution #1: Pell Equation Approach

Let thee nth expansion for the square root of 2 be a/b. Then we would expect a^2 – 2b^2 to be roughly equal to 0. Of course, it can be shown that there are no integers a and b for which the expression is exactly equal to 0, but there are many for which a^2 – 2b^2 = 1 or -1. The first few are a/b = 3/2, 7/5, 17/12, 41/29, etc. These correspond precisely to the expansions for the continued fraction for the square root of 2. It is well known that from the initial solution of a Pell Equation, the rest can be generated recursively. In the case of the square root of 2, it can be shown that if (a,b) is a solution, then (a+2*b)/(a+b) is the next solution. By applying this recursion 1000 times on 3/2, the first 1000 expansions can be analyzed. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Pell Equation Approach to Project Euler Problem #57
 '''
 
 import time
 
 def projectEulerProblemFiftySeven(n):
     numerator = 1
     denominator = 1
     total = 0
     for x in range(n):
         numerator+=2*denominator
         denominator = numerator - denominator
         if(len(str(numerator))>len(str(denominator))):
             total+=1
     return total
 
 start = time.time()
 print projectEulerProblemFiftySeven(1000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 153
 --- 0.00200414657593 seconds ---
 
 for input of n = 1000.
 ''' 

As shown above, Pell Equation recursions can be very handy for evaluating the continued fraction expansions of square roots.

Thanks for reading! See you tomorrow.