; prime anagrams

(define (fold-right op base xs)
  (if (null? xs)
      base
      (op (car xs) (fold-right op base (cdr xs)))))


(define (primes n) ; list of primes not exceeding n
  (let* ((len (quotient (- n 1) 2)) (bits (make-vector len #t)))
    (let loop ((i 0) (p 3) (ps (list 2)))
      (cond ((< n (* p p))
              (do ((i i (+ i 1)) (p p (+ p 2))
                   (ps ps (if (vector-ref bits i) (cons p ps) ps)))
                  ((= i len) (reverse ps))))
            ((vector-ref bits i)
              (do ((j (+ (* 2 i i) (* 6 i) 3) (+ j p)))
                  ((<= len j) (loop (+ i 1) (+ p 2) (cons p ps)))
                (vector-set! bits j #f)))
            (else (loop (+ i 1) (+ p 2) ps))))))

(define ps (list->vector (primes 1620)))

(define (signature str)
  (fold-right (lambda (c n)
               (modulo (* (vector-ref ps (char->integer c)) n)
                       (- (expt 2 31) 1)))
             1
             (string->list str)))

(define (anagram? str1 str2)
  (= (signature str1) (signature str2)))

(display (anagram? "time" "emit"))