[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/YgFEcg8Q    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Nov 29:
; polite numbers

(define (range . args)
  (case (length args)
    ((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
    ((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
    ((3) (let ((le? (if (negative? (caddr args)) >= <=)))
           (let loop ((x(car args)) (xs '()))
             (if (le? (cadr args) x)
                 (reverse xs)
                 (loop (+ x (caddr args)) (cons x xs))))))
    (else (error 'range "unrecognized arguments"))))

(define (filter pred? xs)
  (let loop ((xs xs) (ys '()))
    (cond ((null? xs) (reverse ys))
          ((pred? (car xs))
            (loop (cdr xs) (cons (car xs) ys)))
          (else (loop (cdr xs) ys)))))

(define sort #f)
(define merge #f)
(let ()
  (define dosort
    (lambda (pred? ls n)
      (if (= n 1)
          (list (car ls))
          (let ((i (quotient n 2)))
            (domerge pred?
                     (dosort pred? ls i)
                     (dosort pred? (list-tail ls i) (- n i)))))))
  (define domerge
    (lambda (pred? l1 l2)
      (cond
        ((null? l1) l2)
        ((null? l2) l1)
        ((pred? (car l2) (car l1))
         (cons (car l2) (domerge pred? l1 (cdr l2))))
        (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  (set! sort
    (lambda (pred? l)
      (if (null? l) l (dosort pred? l (length l)))))
  (set! merge
    (lambda (pred? l1 l2)
      (domerge pred? l1 l2))))

(define (unique eql? xs)
  (cond ((null? xs) '())
        ((null? (cdr xs)) xs)
        ((eql? (car xs) (cadr xs))
          (unique eql? (cdr xs)))
        (else (cons (car xs) (unique eql? (cdr xs))))))

(define (ilog b n)
  (let loop1 ((lo 0) (b^lo 1) (hi 1) (b^hi b))
    (if (< b^hi n) (loop1 hi b^hi (* hi 2) (* b^hi b^hi))
      (let loop2 ((lo lo) (b^lo b^lo) (hi hi) (b^hi b^hi))
        (if (<= (- hi lo) 1) (if (= b^hi n) hi lo)
          (let* ((mid (quotient (+ lo hi) 2))
                 (b^mid (* b^lo (expt b (- mid lo)))))
            (cond ((< n b^mid) (loop2 lo b^lo mid b^mid))
                  ((< b^mid n) (loop2 mid b^mid hi b^hi))
                  (else mid))))))))

(define (factors n)
  (if (even? n) (cons 2 (factors (/ n 2)))
    (let loop ((n n) (f 3) (fs '()))
      (cond ((< n (* f f)) (reverse (cons n fs)))
            ((zero? (modulo n f)) (loop (/ n f) f (cons f fs)))
            (else (loop n (+ f 2) fs))))))

(define (divisors n)
  (define (times x) (lambda (y) (* x y)))
  (let divs ((fs (factors n)))
    (unique = (sort <
      (if (null? fs) '(1)
        (let ((ds (divs (cdr fs))))
          (append ds (map (times (car fs)) ds))))))))

(define (polite n d)
  (let ((d2 (quotient d 2)) (n/d (/ n d)))
    (if (< d2 n/d)
        (range (- n/d d2) (+ n/d d2 1))
        (range (+ (abs (- n/d d2)) 1) (+ n/d d2 1)))))

(define (polites n)
  (if (= (expt 2 (ilog 2 n)) n) '()
    (let loop ((ds (cdr (filter odd? (divisors n)))) (ps '()))
      (if (null? ds) (reverse ps)
        (loop (cdr ds) (cons (polite n (car ds)) ps))))))

(define (politeness n)
  (if (= (expt 2 (ilog 2 n)) n) 0
    (length (cdr (filter odd? (divisors n))))))

(display (politeness 15)) (display " ") (display (polites 15)) (newline)
(display (politeness 28)) (display " ") (display (polites 28)) (newline)
(display (politeness 33)) (display " ") (display (polites 33)) (newline)


Output:
1
2
3
3 ((4 5 6) (1 2 3 4 5) (7 8))
1 ((1 2 3 4 5 6 7))
3 ((10 11 12) (3 4 5 6 7 8) (16 17))


Create a new paste based on this one


Comments: