# Solutions for Problem 57

Given the nth continued expansion of the square root of 2 is given by:

```1 + 1/(2 + 1/dn-1)
```

where dn is the denominator of the nth continued expansion, and n1 = 3/2. How many of the reduced proper fractions of the first 1000 expansions have a numerator with more digits than the denominator?

## Lisp/Scheme by SanguineV

Runtime: 3.291 seconds

```; Return the length of an integer
(define (len n)
(if (> 10 n)
1
(+ 1 (len (/ (- n (modulo n 10)) 10)))))

; Given a denominator, return the next one for the continued expansion
(define (nextd d)
(+ 2 (/ 1 d)))

; Check an "e" and return true if the numerator has more digits than the denominator
(define (check e)
((lambda (ne de)
(> (len (/ ne (gcd ne de))) (len (/ de (gcd ne de)))))
(numerator e) (denominator e)))

; Make all the "x" continued expansions starting from some denominator "d"
(define (makeEs x d)
(if (= x 0)
()
(cons (+ 1 (/ 1 d)) (makeEs (- x 1) (nextd d)))))

; Count the number of elements of a list that pass some predicate "f"
(define (count f xs)
(if (null? xs)
0
(if (f (car xs))
(+ 1 (count f (cdr xs)))
(count f (cdr xs)))))

; Display the count of the first 1000 continued expansions that pass the check
(begin (display (count check (makeEs 1000 2))) (newline))
(exit)
```

## Python by Althalus

Runtime: 93ms

```limit = 1000

fraction=[3,2]
count=0
for i in range(1,limit):
fraction[0] += fraction[1]
fraction[0],fraction[1] = fraction[1],fraction[0]
fraction[0] += fraction[1]
if len(str(fraction[0])) > len(str(fraction[1])): count+=1
print count
```