HammingNumbers.java

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

/**
 * An infinite, lazy iterator that produces <em>Hamming numbers</em> (also known
 * as regular numbers or 5-smooth numbers) in ascending order. A Hamming number
 * is a positive integer whose only prime factors are 2, 3, and 5.
 * <p>
 * The sequence begins: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, ...
 * <p>
 * The implementation maintains a priority queue frontier: each time a Hamming
 * number is yielded, its multiples by 2, 3, and 5 are added to the frontier
 * (if not already present). The smallest frontier element is always the next
 * Hamming number — a neat application of best-first search.
 * <p>
 * Implementing {@link Iterable} means you can use this class in a for-each
 * loop, and {@link #stream()} provides access to the full power of the
 * Stream API for filtering, mapping, and collecting.
 *
 * <pre>{@code
 *     // Print the first 20 Hamming numbers:
 *     var hamming = new HammingNumbers();
 *     hamming.stream().limit(20).forEach(System.out::println);
 *
 *     // Use in a for-each loop (careful — it's infinite!):
 *     for (BigInteger h : new HammingNumbers()) {
 *         if (h.bitLength() > 100) break;
 *         System.out.println(h);
 *     }
 * }</pre>
 *
 * @author Ilkka Kokkarinen
 */
public class HammingNumbers implements Iterable<BigInteger> {

    // The three prime factors that define Hamming numbers.
    private static final List<BigInteger> FACTORS = List.of(
            BigInteger.valueOf(2),
            BigInteger.valueOf(3),
            BigInteger.valueOf(5)
    );

    // -----------------------------------------------------------------------
    // Iterable implementation — each call to iterator() produces a fresh,
    // independent iterator that starts from the beginning (1, 2, 3, ...).
    // -----------------------------------------------------------------------

    @Override
    public Iterator<BigInteger> iterator() {
        return new HammingIterator();
    }

    /**
     * Return an infinite sequential {@link Stream} of Hamming numbers.
     * Use {@code .limit(n)} to take a finite prefix.
     *
     * @return a stream of Hamming numbers in ascending order
     */
    public Stream<BigInteger> stream() {
        // Spliterators.spliteratorUnknownSize + StreamSupport is the standard
        // recipe for turning an Iterator into a Stream.
        return StreamSupport.stream(spliterator(), false);
    }

    // -----------------------------------------------------------------------
    // The iterator itself — maintains the priority queue frontier.
    // -----------------------------------------------------------------------

    private static class HammingIterator implements Iterator<BigInteger> {

        // The search frontier, ordered by natural ordering of BigInteger.
        private final PriorityQueue<BigInteger> frontierQueue = new PriorityQueue<>();
        // A parallel set for O(1) duplicate detection.
        private final HashSet<BigInteger> frontierSet = new HashSet<>();

        HammingIterator() {
            // Seed the frontier with 1, the first Hamming number.
            frontierQueue.add(BigInteger.ONE);
            frontierSet.add(BigInteger.ONE);
        }

        /**
         * An infinite iterator always has a next element.
         */
        @Override
        public boolean hasNext() {
            return true; // The Hamming sequence is infinite.
        }

        /**
         * Return the next Hamming number in ascending order, and expand the
         * frontier by adding its multiples by 2, 3, and 5.
         *
         * @return the next Hamming number
         */
        @Override
        public BigInteger next() {
            if (frontierQueue.isEmpty()) {
                // Defensive — should never happen with correct usage.
                throw new NoSuchElementException("Hamming frontier exhausted");
            }

            // Pop the smallest element — this is the next Hamming number.
            BigInteger current = frontierQueue.poll();
            frontierSet.remove(current);

            // Expand: multiply by each factor and add to the frontier if new.
            for (BigInteger factor : FACTORS) {
                BigInteger candidate = current.multiply(factor);
                if (frontierSet.add(candidate)) {
                    // Set.add returns true if the element was not already present.
                    frontierQueue.add(candidate);
                }
            }

            return current;
        }
    }

    // -----------------------------------------------------------------------
    // Convenience: compute the n-th Hamming number (1-indexed).
    // -----------------------------------------------------------------------

    /**
     * Return the {@code n}-th Hamming number (1-indexed), so
     * {@code nth(1) = 1}, {@code nth(2) = 2}, {@code nth(6) = 6}, etc.
     *
     * @param n the 1-based index
     * @return the n-th Hamming number
     * @throws IllegalArgumentException if n is less than 1
     */
    public BigInteger nth(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("Index must be >= 1, got: " + n);
        }
        return stream().skip(n - 1).findFirst().orElseThrow();
    }

    // -----------------------------------------------------------------------
    // Main — demonstrate various ways to use the iterator.
    // -----------------------------------------------------------------------

    public static void main(String[] args) {
        var hamming = new HammingNumbers();

        // --- For-each loop (the simplest usage) ---
        System.out.println("First 20 Hamming numbers (for-each loop):");
        int count = 0;
        for (BigInteger h : hamming) {
            System.out.print(h + " ");
            if (++count >= 20) break;
        }
        System.out.println("\n");

        // --- Stream with limit ---
        System.out.println("First 20 Hamming numbers (stream):");
        hamming.stream()
                .limit(20)
                .forEach(h -> System.out.print(h + " "));
        System.out.println("\n");

        // --- Finding a specific one ---
        System.out.println("The 1000th Hamming number:");
        long startTime = System.currentTimeMillis();
        BigInteger h1000 = hamming.nth(1000);
        long elapsed = System.currentTimeMillis() - startTime;
        System.out.printf("%s (%d ms)%n%n", h1000, elapsed);

        // --- Stream filtering: Hamming numbers that are also perfect squares ---
        System.out.println("First 15 Hamming numbers that are perfect squares:");
        hamming.stream()
                .filter(h -> {
                    BigInteger sqrt = h.sqrt();
                    return sqrt.multiply(sqrt).equals(h);
                })
                .limit(15)
                .forEach(h -> System.out.print(h + " "));
        System.out.println("\n");

        // --- Demonstrate that each iterator() call is independent ---
        System.out.println("Two independent iterators:");
        var iter1 = hamming.iterator();
        var iter2 = hamming.iterator();
        System.out.print("iter1: ");
        for (int i = 0; i < 10; i++) { System.out.print(iter1.next() + " "); }
        System.out.print("\niter2: ");
        for (int i = 0; i < 10; i++) { System.out.print(iter2.next() + " "); }
        System.out.println();
    }
}