# Euler Solution 57

### From ProgSoc Wiki

# Solutions for Problem 57

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

1 + 1/(2 + 1/d_{n-1})

where d_{n} is the denominator of the nth continued expansion, and n_{1} = 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