Euler Solution 57

From ProgSoc Wiki

Jump to: navigation, search

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 (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)
    (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))

Python by Althalus

Runtime: 93ms

limit = 1000

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
Personal tools