; strangers on a train (define (take n xs) (let loop ((n n) (xs xs) (ys '())) (if (or (zero? n) (null? xs)) (reverse ys) (loop (- n 1) (cdr xs) (cons (car xs) ys))))) (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 (last xs) (if (null? xs) (error 'last "empty list") (let loop ((xs xs)) (if (null? (cdr xs)) (car xs) (loop (cdr xs)))))) (define (remove x xs) (let loop ((xs xs) (zs '())) (cond ((null? xs) (reverse zs)) ((equal? (car xs) x) (loop (cdr xs) zs)) (else (loop (cdr xs) (cons (car xs) zs)))))) (define (all? pred? xs) (cond ((null? xs) #t) ((pred? (car xs)) (all? pred? (cdr xs))) (else #f))) (define (prime? n) (let loop ((d 2)) (cond ((< n (* d d)) #t) ((zero? (modulo n d)) #f) (else (loop (+ d 1)))))) (define (next-prime n) (let ((n (+ n 1))) (if (prime? n) n (next-prime n)))) (define (coprime? x y) (= (gcd x y) 1)) (define (strangers n) (let loop1 ((k 1) (strange (list 2)) (avail (list 3 4))) (if (<= n k) (reverse strange) (let loop2 ((cs avail)) ; list of candidates (if (null? cs) (error 'strangers "null candidate list") (let ((c (car cs))) (if (all? (lambda (x) (coprime? x c)) (take (quotient (+ k 1) 2) strange)) (loop1 (+ k 1) (cons c strange) (append (remove c avail) (range (+ (last cs) 1) (+ (next-prime (last cs)) 1)))) (loop2 (cdr cs))))))))) (display (strangers 61))