[Edu-sig] re: TeachScheme

[Kirby Urner]

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