Problem #64 is another Project Euler problem that concerns infinite continued fractions for irrational numbers. The question reads:
I apologize for not embedding the wording of the problem within WordPress. I was a bit lazy this time because the problem was so long. This is a good example of when a coding problem gives too many examples to build an understanding. Regardless, my solution for this problem involves a bit of arbitrary brute force with the “decimal” library in Python. Here’s my solution:
Solution #1: Arbitrary Precision Approach
We simply use the Python decimal library to get very precise values of the irrational square roots of every number less than 10,000 and evaluate the continued fraction for those precise square roots until a loop is found. This is a very risky approach because in the event that the value is not precise enough, the program could run into an infinite loop for the continued fraction or the values within the continued fraction could get too big for the program to store them accurately. As a result, I had to guess and check what level of precision was needed. Here is an implementation of this approach in Python 2.7 with the decimal library:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #64
'''
import time
from math import floor
from decimal import *
getcontext().prec = 214
def gcd(a,b):
if(a<0 or 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 projectEulerProblemSixtyFour(n):
total = 0
for e in range(2,n+1):
v = Decimal(e).sqrt()
if(int(v)*int(v)!=e):
fractions = []
root = [1,1]
constant = [0,1]
denominators = []
while [root,constant] not in fractions:
fractions.append([root,constant])
a = root[0]
b = root[1]
c = constant[0]
d = constant[1]
x = int(floor(v))
denominators.append(x)
v = Decimal(1.)/(Decimal(v)-Decimal(int(v)))
newRootN = a*b*d*d
newRootD = a*a*d*d*e-b*b*c*c-x*x*b*b*d*d+2*b*b*x*c*d
newConstantN = x*b*b*d*d-b*b*c*d
newConstantD = newRootD
g1 = gcd(newRootN,newRootD)
g2 = gcd(newConstantN,newConstantD)
newRootN/=g1
newRootD/=g1
newConstantD/=g2
newConstantN/=g2
if(newRootD<0):
newRootN = -newRootN
newRootD = -newRootD
if(newConstantD<0):
newConstantD = -newConstantD
newConstantN = -newConstantN
root = [newRootN,newRootD]
constant = [newConstantN,newConstantD]
period = len(fractions) - fractions.index([root,constant])
if(period%2==1):
total+=1
return total
start = time.time()
print projectEulerProblemSixtyFour(10000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
1322
--- 12.4575679302 seconds ---
for input of n = 10000.
'''
And with that, we’re done. I needed 214 digits after the decimal point to precisely calculate the repeated continued fractions of all the square roots in this range. As a result, the program took over 12 seconds to run. I would definitely like to return to this problem to find an approach that does not use arbitrary precision, but it is good to know about Python libraries that allow for extra precision such as decimal.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 