```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ``` ```; factoring with bicycle chains (define (isqrt n) (if (not (and (positive? n) (integer? n))) (error 'isqrt "must be positive integer") (let loop ((x n)) (let ((y (quotient (+ x (quotient n x)) 2))) (if (< y x) (loop y) x))))) (define (square x) (* x x)) (define (every? xs) (if (null? xs) #t (if (not (car xs)) #f (every? (cdr xs))))) (define (last-pair xs) (if (null? (cdr xs)) xs (last-pair (cdr xs)))) (define (cycle xs) (set-cdr! (last-pair xs) xs) xs) (define (chain n len) (let ((a (+ (isqrt n) 1)) (qs (make-vector len #f)) ; quadratic residue? (cs (make-vector len #f))) ; chain link has peg? (do ((i 0 (+ i 1))) ((= i len)) (vector-set! qs (modulo (square i) len) #t)) (do ((i 0 (+ i 1))) ((= i len) (cycle (vector->list cs))) (vector-set! cs i (vector-ref qs (modulo (- (square (+ a i)) n) len)))))) (define (bicycle n chains) (let loop ((a (+ (isqrt n) 1)) (cs (map (lambda (len) (chain n len)) chains))) (if (not (every? (map car cs))) (loop (+ a 1) (map cdr cs)) (let* ((b2 (- (square a) n)) (b (isqrt b2))) (if (= (square b) b2) (list (- a b) (+ a b)) (loop (+ a 1) (map cdr cs))))))) (define chains ; lehmer's 19-chain machine '(64 27 25 49 22 26 17 19 23 29 31 37 41 43 47 53 59 61 67)) (display (bicycle 5237178673 chains)) ```
 ```1 ``` `(64433 81281)`