hcn

Find highly composite numbers up to a search limit.

cargo run --release -- [SEARCH_LIMIT]

If no limit is given, the default is 1_000_000_000. Use --help to see the generated command-line help and --version to print the package version.

Structure

• src/main.rs
  • Command-line interface: parses the optional SEARCH_LIMIT argument with clap and rejects non-positive limits before the search starts.
  • Search setup: defines the default limit and the fixed prime list used for candidate generation.
  • Candidate generation: recursively builds only exponent sequences that can produce highly composite record candidates.
  • Record filtering: sorts candidates and prints each new divisor-count record.

Algorithm

A number with prime factorization

n = 2^a * 3^b * 5^c * ...

has

(a + 1) * (b + 1) * (c + 1) * ...

divisors.

The exact primes do not affect the divisor count; only the exponents do. For a fixed exponent list, the smallest possible number is made by putting the largest exponent on the smallest prime:

a >= b >= c >= ...

If a larger exponent appears on a larger prime, swapping those two exponents keeps the divisor count unchanged but makes the number smaller.

So a highly composite number cannot have that shape. If it did, the smaller swapped number would already have the same number of divisors, so the original number would not be the first record.

That means record candidates are only numbers like:

2^a * 3^b * 5^c * ...  where a >= b >= c >= ...

All other numbers are redundant for finding new records.

The program:

1. Recursively generates numbers from the first primes.
2. Only tries exponent sequences where each exponent is no larger than the previous one.
3. Stops a branch as soon as the number exceeds the search limit.
4. Computes the divisor count directly from the exponents.
5. Sorts candidates by number and prints each new divisor-count record.

This avoids factoring every number in the range.