Programming Praxis

We will use the sum-div function of the prior exercise, including the wheel factorization algorithm used there; you could use some more powerful factoring algorithm if you like. Here is our function:

(define (aliquot n)
  (define (rotate xs)
    (if (= (car xs) (apply min xs)) xs
      (rotate (append (cdr xs) (list (car xs))))))
  (when verbose? (display n) (display ",0: ")
    (display n) (newline))
  (let loop ((s (sum-div n)) (ss (list n)) (k 1))
    (when verbose? (display n) (display ",")
      (display k) (display ": ") (display s) (newline))
    (cond ((= s 1) (car ss))
          ((member s ss) (rotate (member s (reverse ss))))
          (else (loop (sum-div s) (cons s ss) (+ k 1))))))

Here are three simple examples:

> (aliquot 12)
12,0: 12
12,1: 16
12,2: 15
12,3: 9
12,4: 4
12,5: 3
12,6: 1
3
> (aliquot 25)
25,0: 25
25,1: 6
25,2: 6
(6)
> (aliquot 562)
562,0: 562
562,1: 284
562,2: 220
562,3: 284
(220 284)

Two more interesting examples are shown on the next page: (aliquot 168) terminates in the prime 59 after 174 steps, and (aliquot 17490) terminates in the four-cycle (1264460 1547860 1727636 1305184) after 232 steps.

Aliquot sequences are an object of continuing study in the realm of computational number theory. Mathematicians talk about aliquot families of numbers that terminate in the same aliquot sequence, and there are many numbers with unknown termination, including the famous Lehmer five: 276, 552, 564, 660, 966.

You can run the program at http://programmmingpraxis.codepad.org/NEbLYA6y.

Pages: 1 2 3