# Euler Solution 72

### From ProgSoc Wiki

(Difference between revisions)

(→SOlutions for Problem 72) |
|||

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. |

## Revision as of 00:02, 26 April 2010

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