1 ! Copyright (c) 2008 Samuel Tardieu
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.parser project-euler.common sequences ;
6 ! https://projecteuler.net/problem=57
11 ! It is possible to show that the square root of two can be
12 ! expressed as an infinite continued fraction.
14 ! √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
16 ! By expanding this for the first four iterations, we get:
19 ! 1 + 1/(2 + 1/2) = 7/5 = 1.4
20 ! 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
21 ! 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
23 ! The next three expansions are 99/70, 239/169, and 577/408, but
24 ! the eighth expansion, 1393/985, is the first example where the
25 ! number of digits in the numerator exceeds the number of digits
28 ! In the first one-thousand expansions, how many fractions
29 ! contain a numerator with more digits than denominator?
34 : longer-numerator? ( seq -- ? )
35 >fraction [ number>string length ] bi@ > ; inline
37 : euler057 ( -- answer )
38 0 1000 <iota> [ drop 2 + recip dup 1 + longer-numerator? ] count nip ;
40 ! [ euler057 ] 100 ave-time
41 ! 1728 ms ave run time - 80.81 SD (100 trials)