Apropos our recent thread, I was inspired to boot DrScheme and challenge myself to oil the rusty wheel works (i.e. my brain) enough to crank out a small Scheme program for totient(n) -- or as Schemers would write it: (totient n). Then I did the same in Python. Then I modified both. Then I explained how this isn't the "best" algorithm in either case (but maybe we'll get to that later): http://www.mathforum.org/epigone/k12.ed.math/gaupholflo For those who've read a lot of my stuff over the years, it's the same old same old. I don't seem to get tired of it. Kirby PS: here's the code I ended up with: Scheme: ;; totient : integer -> integer ;; compute the number of positives < n that are ;; relatively prime to n (define (totient n) (if (not (and (integer? n)(>= n 0))) "Incorrect input" (begin (let loop ((tot 0)(pos n)) (if (> pos 0) (loop (+ tot (if (= 1 (gcd n pos)) 1 0)) (- pos 1)) tot ) ) ) ) ) Python: def totient(n): """ count totatives of n, assuming gcd already defined """ if not (type(n)==type(1) and n>=0): raise ValueError, 'Invalid input type' tot,pos = 0, n while pos>0: if gcd(pos,n)==1: tot += 1 pos -= 1 return tot