76 lines
2.0 KiB
Python
76 lines
2.0 KiB
Python
#!/usr/bin/python
|
|
|
|
# The square root of 2 can be written as an infinite continued fraction.
|
|
#
|
|
# √2=1+1/(2+1/(2+1/(2+1/(2+...
|
|
#
|
|
# The infinite continued fraction can be written, √2=[1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √23=[4;(1,3,1,8)].
|
|
# It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations.
|
|
# Let us consider the convergents for √22.
|
|
#
|
|
# 1+1/2=3/2
|
|
# 1+1/(2+1/2)=7/5
|
|
# 1+1/(2+1/(2+1/2))=17/12
|
|
# 1+1/(2+1/(2+1/(2+1/2)))=41/29
|
|
#
|
|
# Hence the sequence of the first ten convergents for √2 are:
|
|
#
|
|
# 1,3/2,7/5,17/12,41/29,99/70,239/169,577/408,1393/985,3363/2378,...
|
|
#
|
|
# What is most surprising is that the important mathematical constant,
|
|
#
|
|
# e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...].
|
|
#
|
|
# The first ten terms in the sequence of convergents for e are:
|
|
#
|
|
# 2,3,8/3,11/4,19/7,87/32,106/39,193/71,1264/465,1457/536,...
|
|
#
|
|
# The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.
|
|
#
|
|
# Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
@timing
|
|
def p065():
|
|
ai = [1, 2, 1]
|
|
count = 4
|
|
|
|
n0 = 3
|
|
n1 = 8
|
|
n2 = 11
|
|
|
|
# For a continued fractions [a_0; a_1, a_2, ...], the numerator of the
|
|
# next convergent N_n=a_n*N_(n-1)+N_(n-2). The first three values for e are
|
|
# 3, 8 and 11, the next ones are easily calculated, considering that a_n
|
|
# follows a simple pattern:
|
|
# a_1=1, a_2=2, a_3=1
|
|
# a_4=1, a_5=4, a_6=1
|
|
# a_7=1, a_8=6, a_9=1
|
|
# and so on.
|
|
while count < 100:
|
|
ai[1] = ai[1] + 2
|
|
|
|
for i in range(3):
|
|
n0 = n1
|
|
n1 = n2
|
|
n2 = n1 * ai[i] + n0
|
|
count = count + 1
|
|
|
|
if count >= 100:
|
|
break
|
|
|
|
sum_ = 0
|
|
|
|
while n2 != 0:
|
|
sum_ = sum_ + n2 % 10
|
|
n2 = n2 // 10
|
|
|
|
print('Project Euler, Problem 65')
|
|
print(f'Answer: {sum_}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p065()
|