Задача Хэмминга о порождении чисел

Существует знаменитая задача, впервые сформулированная Р. Хэммингом: породить в возрастающем порядке и без повторений все положительные целые числа, у которых нет других простых делителей, кроме 2, 3 и 5 . Очевидное решение состоит в том, чтобы перебирать все натуральные числа по очереди и проверять, есть ли у них простые множители помимо 2, 3 и 5 . Однако эта процедура весьма неэффективна, поскольку чем больше числа, тем меньшая их доля соответствует условию. Применим альтернативный подход: назовем искомый поток чисел S и обратим внимание на следующие факты:

• S начинается с 1 .

• Элементы (scale-streams 2) также принадлежат S .

• То же верно и для (scale-stream S 3) и (scale-stream S 5) .

• Других элементов S нет.

Теперь требуется только соединить элементы из этих источников. Для этого мы определяем процедуру merge , которая сливает два упорядоченных потока в один упорядоченный поток, убирая при этом повторения:

(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))

Тогда требуемый поток можно получить с помощью merge таким образом:

(define S (cons-stream 1 (merge <??> <??>)))

Заполните пропуски в местах, обозначенных знаком <??> .

---