Convergents of e

2015-07-08

Problem 065: Convergents of e

Description:

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).

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 sqrt(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.

Solution:

v $$$    #######################################################################

         #######################################################################

    v                 -1<
>"F">:9+"0"\0p:9+"0"\2p:|
v"c"p040p2"O1"p0"O0"   $<
          >$1         v@.<v02-"0"p0g03:g2g03-"0"g0:p03:<-1<
  >:1-3%:!|   >:1+3/2*v  +>g*+40g+:55+%"0"+30g2p55+/40p:9-|
>:|       >2-#^_1     >20 p                      "O"v  #  $
| ># #+ #1 #: #- #12# ^#                            ># ^# <
$               >\v  >\:!|
>0"F">:9+2g"0"-:| >:!|1 +<
     ^        -1_ ^#1<

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

Nice algorithm if you see the pattern in the numerators and denominators.

denom(n+1) = denom(n) + numer(n) * frac(n)
numer(n+1) = denom(n)

and the fraction at position n is calculated by (OEIS-A003417):

int GetFrac(int idx)
{
    if (idx == 0) return 2;
    if ((idx-1) % 3 == 0) return 1;
    if ((idx-1) % 3 == 1) return ((idx+1)/3)*2;
    if ((idx-1) % 3 == 2) return 1;
    return 2;
}

The rest is just multiplication and long addition (we exceed the 64bit range) a hundred times ...

Interpreter steps:	477 489
Execution time (BefunExec):	124ms (3.85 MHz)
Program size:	80 x 14 (fully conform befunge-93)
Solution:	272
Solved at:	2015-07-08