Square root convergents

2015-05-07

Problem 057: Square root convergents

Description:

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2                         = 3 /2  = 1.5
1 + 1/(2 + 1/2)                 = 7 /5  = 1.4
1 + 1/(2 + 1/(2 + 1/2))         = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Solution:

v

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

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

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

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

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

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

>77*8*2+>:0\:"O"%1+\"O"/2+p:0\:"O"%1+\"O"/8+p:0\:"O"%1+\"O"/72*+p:0\:   v
        |+1:-1p+*84/"O"\+1%"O":\0:p++*298/"O"\+1%"O":\0:p+*45/"O"\+1%"O"<
        >$ 1"O"6p1"O"62*p1"O"56*p v
v                                 <
>60*70p61*80p62*90p60*71p61*81p v                  >   0>$                 v
v*"o"9 p040p121p111p19*26       <                  ^p11_^#`g11 :-g02*5"O"<
> 010p"O"5*>1-:::20p:"O"%1+\"O"/70g2++g\:"O"%1+\"O"/80g2++g2*10g++:55+%:#^_v
           ^                              _v#:p01/+55p++2g09/"O"\+1%"O":g02<
v    p09%+99+6g09p08%+99+6g08p07%+99+6g07$<           >   0>$                 v
                                                       ^p12_^#`g12 :-g02*5"O"<
>010p"O"5*>1-:::20p:"O"%1+\"O"/71g54*++g\:"O"%1+\"O"/81g54*++g2*10g++:55+%:#^_v
           ^                                _v#:p01/+55p++*45g19/"O"\+1%"O":g02<
v      p19%+99+6g19p18%+99+6g18p17%+99+6g17$<
>11g21g`!#v_40g1+40pv
|:       -1<         <
>$40g.@

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

I was a bit lazy with this problem. The first thing i did was search on OEIS for the numerator and denominator sequences. And I found both, they are A123335 and A000129. But still there are two mayor problems:

First these are recursive functions, so we need to store the last and the second last result. This is again the reason why our programs exceeds the Befunge-93 size restrictions. We need three fields for the numerator and three for the denominator (Current value | Last value | Second last value).
Second the numbers become big. Like really big. The last values get close to four hundred digits. So - again - we need to do the calculations manually (long multiplication and addition)

In the end we have a reasonable fast program with six 79*5 arrays for value storage.