Project Euler 65: Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Project Euler 65: Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Written by on 15 October 2011

Topics: Project Euler

They really went crazy with the whole continued fractions theme. Project Euler‘s problem 65 as this one is about the continued fraction of e. The problem reads

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 √2.

1 +
1
= 3/2
2
1 +
1
= 7/5
2 +
1
2
1 +
1
= 17/12
2 +
1
2 +
1
2
1 +
1
= 41/29
2 +
1
2 +
1
2 +
1
2

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.

We are only interested in the numerator, and if we investigate that we will rather quickly find a patter which is consistent with given continued fraction for e. The pattern is

As we can also see the continued fraction forms a regular pattern where every third increases by two and the rest are ones. This means we can write a small piece of code that will give us the numerator. The C# implementation looks like

int upperbound = 100;
int result = 0;

BigInteger d = 1;
BigInteger n = 2;

for (int i = 2; i <= upperbound; i++) {
    BigInteger temp = d;
    int c = (i % 3 == 0) ? 2 * (i / 3) : 1;
    d = n;
    n = c * d + temp;
}
result = DigitSum(n);

with the DigitSum function being something that was developed for a previous problem so you can check that out in the source code. Executing this code yields the following result, and not surprisingly it is blazing fast since the number of computations we need to do is really small.

The digit sum of the numerator of the 100th convergent is 272
Solution took 0 ms

Wrapping up

This problem was a rather easy and fast solved on, so I don’t have a lot of fancy things to add to it.  As always you are more than welcome to take a look at the whole source code and come with comments if you spot mistakes, faster way or ask questions if I don’t explained something well enough. How did you approach this problem?

2 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

    Table 1
    Continued fraction for e.
    Convergents of e numerators: sum and number of digits.

    http://img15.hostingpics.net/pics/319863PE65tableonecffore.jpg

    As expected, Table 1 shows that the averages of the ratio (SOD)/(NOD) are getting closer to 4,5 (0+1+2+3+4+5+6+7+8+9=45; 45/10=4,5) as the sequence increases.
    ___

    By the way, over 500 billon digits of e have been computed (5).
    Excerpt:
    « e – Computation + Verification: 12 days, 19 hours. »
    http://www.numberworld.org/misc_runs/e-500b.html

    ___

    Sources:

    1) Project Euler 143
    Kristian’s algorithm.
    http://www.mathblog.dk/files/euler/Problem65.cs
    2) Microsoft Visual C# 2010 Express
    (Reference added: System.Numerics)
    3) A007676 Numerators of convergents to e.
    (Formerly M0869)
    https://oeis.org/A007676
    4) OEIS, lilst.
    Eric W. Weisstein, Table of n, a(n) for n = 0..1000 (first 200 terms from T. D. Noe)
    https://oeis.org/A007676/b007676.txt
    5) Microsoft Office Excel (2007)
    6) “Announcing 500 billion digits of e…”
    The first world record size computation of a major constant on an overclocked computer.
    By Alexander J. Yee
    Department of Electrical Engineering and Computer Science
    Northwestern University, Evanston, IL, 60201
    (Last updated: March 7, 2011)
    http://www.numberworld.org/misc_runs/e-500b.html

  2. Myrtonos says:

    I know that e can be approximated by adding 1 to the reciperocals of factorals up to a certain amount. In between convergents there a semi-convergents are 49/18 = [2; 1, 2, 1, 1, 2] and 68/25 = [2; 1, 2, 1, 1, 3].
    Convergents and semi-convergents are always closer to the so called “true” value than any other with a lesser denominator value.

    By the way, over 500 billon digits of e have been computed.

    No, actually, it’s a 500 billion digit decimal approximation. The decimal system, introdcuced by Simon Stevin in the 16th century only works for rational numbers.

    An infinite sequence of non-repeating decimals does not really compute.

    As noted above, the continued fractions of quadratic irrationals can be encoded by completely finite expressions, in case of the square root of 3, it’s [3;{1, 2}]. The CF expansion of e can be similarly encoded as
    [2;{1, 2k, 1}] where k is the index of the period interation. Again this is finite.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.