For a finite nonempty collection of exact real multipliers greater than one, the multiplicative closure of one can be enumerated by a shared lazy list: emit one, then merge its elementwise multiples by all generators. Every value after one has a smaller predecessor obtained by removing one factor, proving productivity by increasing value. There are only finitely many exponent tuples below any fixed bound, because every generator is greater than one; thus locally finite sorted-stream merge eventually emits every generated value. Equal products are emitted once.
A multiplier below one contradicts increasing order starting at one. A multiplier equal to one adds no new values and should be removed from the recursive streams; an empty remaining generator collection has the finite closure consisting of one. These qualifications concern exact arithmetic: finite precision or overflow can violate the order and growth assumptions.
The Hamming number stream merges its shared multiples by two, three and five. To emit its first values, each of the fixed number of mapped streams and merge nodes advances at most positions. With lazy evaluation that shares each evaluated list cell, this takes comparisons and fixed-factor multiplications. The statement counts arithmetic operations, rather than bits: the growing exact integers make their bit-operation costs larger. Recomputing independent copies of the recursively defined stream loses this sharing argument.
Articles by others on the same topic
There are currently no matching articles.