Project Euler — Problem 65 Solution

Problem

The square root of 2 can be writ­ten as an infi­nite con­tin­ued frac­tion.

image7

The infi­nite con­tin­ued frac­tion can be writ­ten, ?2 = [1;(2)], (2) indi­cates that 2 repeats ad infini­tum. In a sim­i­lar way, ?23 = [4;(1,3,1,8)].

It turns out that the sequence of par­tial val­ues of con­tin­ued frac­tions for square roots pro­vide the best ratio­nal approx­i­ma­tions. Let us con­sid­er the con­ver­gents for ?2.

image11

Hence the sequence of the first ten con­ver­gents 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 sur­pris­ing is that the impor­tant math­e­mat­i­cal con­stant,

e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

The first ten terms in the sequence of con­ver­gents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of dig­its in the numer­a­tor of the 10th con­ver­gent is 1+4+5+7=17.

Find the sum of dig­its in the numer­a­tor of the 100th con­ver­gent of the con­tin­ued frac­tion for e.

Solution

If you look at the con­ver­gents of ?2 and the numer­a­tors in the con­ver­gents of e, you’ll see a pat­tern emerg­ing:

1    +    2    *   1    =    3

2    +    3    *   2    =    8

3    +    8    *   1    =    11

8    +   11   *   1    =    19

11  +   19   *   4    =    87

If you look at the sequence of numer­a­tors in the con­ver­gents of e ( 2, 3, 8, 11, … ) and the sequence of num­bers in the con­ver­gents of ?2 ( 1, 2, 1, 1, 4, 1, … ), giv­en the cur­rent numer­a­tor ( n ) and the pre­vi­ous numer­a­tor ( n-1 ) in the sequence and the cor­re­spond­ing num­ber in the con­ver­gents of ?2 ( i )the next numer­a­tor ( n+1 ) can be cal­cu­lat­ed using the for­mu­la:

( n+1) = ( n-1 ) + n * i

Once we have this for­mu­la to work with, the rest is sim­ple, the solu­tion runs in 7 mil­lisec­onds on my machine.