Euler Solution 72

From ProgSoc Wiki

Jump to: navigation, search

SOlutions for Problem 72

How many elements would be contained in the set of reduced proper fractions for d 1,000,000?

Scheme by Althalus

Runtime: 4 hours. Algorithm is identical to my solution for problem 73. Stern-Brocot tree, starting from 0/1 and 1/1. More efficient would be phi(2)+phi(3)+...+phi(n), but I have yet to write a decently good enough solution for phi.

#lang scheme

(define (stern-brocot depth n1 d1 n2 d2 curdepth)
  (define n (+ n1 n2))
  (define d (+ d1 d2))
  (cond
    [(or (> n d) (> d depth))
     0]
    [else
     (cond
       [(<= curdepth depth)
        (+ 1 (+ (stern-brocot depth n d n2 d2 (+ curdepth 1)) (stern-brocot depth n1 d1 n d (+ curdepth 1))))]
       [else 1])
     ])
)

(stern-brocot 1000000 0 1 1 1 1)
Personal tools