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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript