Skip to main content

Project Euler Problem 65 Solution with python

Convergents of e

The square root of 2 can be written as an infinite continued fraction. $$ \begin{equation} \sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2....} } } } \end{equation} $$ The infinite continued fraction can be written, $ \sqrt{2} = [1;(2)]$, (2) indicates that 2 repeats ad infinitum. In a similar way, $\sqrt{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 $\sqrt{2}$. \begin{equation} 1 + \cfrac{1}{2} = \cfrac{3}{2}\end{equation} \begin{equation} 1 + \cfrac{1}{2 + \cfrac{1}{2}} = \cfrac{7}{5} \end{equation} \begin{equation} 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2} } } = \cfrac{17}{12} \end{equation} \begin{equation} \sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2} } } } = \cfrac{41}{29} \end{equation} Hence the sequence of the first ten convergents for $\sqrt{2}$ are:
$1, \cfrac{3}{2}, \cfrac{7}{5}, \cfrac{17}{12}, \cfrac{41}{29},\cfrac{99}{70}, \cfrac{239}{169}, \cfrac{577}{408}, \cfrac{1393}{985}, \cfrac{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, \cfrac{8}{3}, \cfrac{11}{4}, \cfrac{19}{7}, \cfrac{87}{32},\cfrac{106}{39}, \cfrac{193}{71}, \cfrac{1264}{465}, \cfrac{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.

Generating the values inside the continued fraction for $ e $ is easy because the same has been given in the question. The tricky part in this problem is to convert a kind of mixed fraction to a simple fraction.

The best way to understand the algorithm is by taking an example.

Consider that we will have to find the value of simple fraction for the continued fraction:

\begin{equation} 3 + \cfrac{1}{5 + \cfrac{1}{9 + \cfrac{1}{4 + \cfrac{1}{2} } } } \end{equation}

And representing the Continued fraction in terms of [] we can write the above continued fraction as: $$ [3; 5, 9, 4, 2] $$ To find the simple fraction, we will start from the last element $2$.

Now $4 + \cfrac{1}{2} = \cfrac{9}{2}$

Continuing further we have $9 + \cfrac{1}{\cfrac{9}{2}} = 9 + \cfrac{2}{9} = \cfrac{83}{9}$

$\implies 5 + \cfrac{1}{\cfrac{83}{9}} = 5 + \cfrac{9}{83} = \cfrac{424}{83}$
$\implies 3 + \cfrac{1}{\cfrac{424}{83}} = 3 + \cfrac{83}{424} = \cfrac{1355}{424}$
A very big number and a lot of calculation! But I hope you have understood the point.

If you have observed, for every step in solving we are reversing the numerator and the denominator.

Based on our experience till now we will write a function which will take three inputs, numerator, denominator and the number to which this is to be added.

In [1]:
# http://radiusofcircle.blogspot.com
def continued_fraction_inv(a, numerator, denominator):
    return a*denominator+numerator, denominator

For example to find the total fractional value of $5 + \cfrac{83}{507}$ we will give a = 5, numerator = 83, denominator = 507. We will see this in action.

You can download the code from Github Gist continued_fraction_inv.py

In [2]:
print continued_fraction_inv(5, 83, 507)

(2618, 507)

The output is as expected. We are getting the same result as we have when calculated using pen and paper. This is the main concept of the algorithm which I have used to solve this problem.

Program

In [ ]:
# http://radiusofcircle.blogspot.com

# time module
import time

# time at the start of program execution
start = time.time()

# exponent continued fraction
e = [2,]

# iterator
i = 1

# while loop to get 100 numbered list
while len(e) < 100:
    e.extend([1, 2*i, 1])
    i += 1

# initial numerator
numerator = 1

# last number of the list as denominator
denominator = e.pop()

# looping through the list to get the convergents
for i in e[::-1]:
    denominator, numerator =  (denominator * i + numerator, denominator)

# finding the answer
# remember denominator is the new numerator
print sum([int(digit) for digit in str(denominator)])

# time at the end of program execution
end = time.time()

# print total time taken
print end - start

The program is very much simple. As we have discussed in the previous section, for each and every iteration denominator will become the numerator and vice versa. Also at the end we are using the denominator to find the solution. To get a clear cut understanding of what is happening behind the scenes, you can do two things:

  • Print the value for of numerator and denominator for each and every iteration
  • Reduce the list size upto 5 elements and write the output for each and every iteration.

My suggestion would be to choose the second option.

You can download the program from here: Github Gist pep65.py

Output

Summary

As most of the data have already been given in the question, solving the problem was relatively easier. When I first attempted to solve this problem I didn't read the question properly and tried finding the CF of exponent using other methods. After a few trials I read the question once again and it worked. The solution was already in the question. I am well satisfied with the execution time of the program.

If you have any doubt or didn't understand anything, comment in the comment box below and I will be glad to help you.

If you have found a typo or have a better/different approach to solving this problem, please share your code in the comment box below and I will very happy to see your comment.

You can also contact me.

Thank you. Have a nice day😃.

Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more