Euler Solution 72
From ProgSoc Wiki
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)