Project Euler Problem #65

Problem #65 concerns the infinite continued fraction for e. The question reads:

Once again, I apologize for not embedding this problem in WordPress. The problem had a ton of LaTeX this time and I thought it would be easier to just upload a screenshot. Unfortunately, the continued fractions for e cannot be reduced to solving a Pell Equation like the continued fractions for irrational square roots. Therefore, my solution uses brute force to get an answer.

Solution #1: Brute Force Approach

We simply evaluate the exact 100th expansion of the continued fraction for e. In case you cannot tell, the continued fraction for e can be written in the form e = [1,0,1,1,2,1,1,4,1,1,6,1,1,8,1,1,10, … 1,1,2k, …]. Here is a proof of this continued fraction: Link. Thus, the 100th continued fraction is composed of the first 101 terms of this array. Therefore, all we have to do is list the first 101 terms of this array and work backwards, simplifying any reducible fractions we encounter. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #65
 '''
 
 import time
 
 def gcd(a,b):
     if(min(a,b)<0):
         return gcd(abs(a),abs(b))
     if(min(a,b)==0):
         return max(a,b)
     if(a>b):
         return gcd(b,a%b)
     return gcd(a,b%a)
 
 def projectEulerProblemSixtyFive(n):
     denominatorList = [1,0]
     for c in range(n):
         if(c%3==2):
             denominatorList.append((c+1)*2/3)
         else:
             denominatorList.append(1)
     curNumerator = 1
     curDenominator = 0
     order = denominatorList[::-1]
     for x in order:
         n = curDenominator+curNumerator*x
         d = curNumerator
         g = gcd(n,d)
         if(g==0):
             g = 1
         curNumerator = n/g
         curDenominator = d/g
     total = 0
     for x in str(curNumerator):
         total+=int(x)
     return total
 
 start = time.time()
 print projectEulerProblemSixtyFive(100)
 print ("--- %s seconds ---" % (time.time() - start))
 
 '''
 Prints
 
 272
 --- 0.00275802612305 seconds ---
 
 for input of n = 100.
 ''' 

For context, the exact numerator of this expansion is 6963524437876961749120273824619538346438023188214475670667. Thus, while this approach may work fine in Python, it will probably require some clever implementation in languages that cannot store numbers this large. Regardless, this method runs quite quickly in Python 2.7.

Thanks for reading! See you tomorrow.