# Euler Solution 72

(Difference between revisions)
 Revision as of 00:02, 26 April 2010 (view source)Althalus (Talk | contribs)← Older edit Revision as of 00:02, 26 April 2010 (view source)Althalus (Talk | contribs) (→SOlutions for Problem 72)Newer edit → Line 1: Line 1: = SOlutions for Problem 72 = = 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 == == 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. 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.

# 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)
```