Detailed mathematical approach

Problem Summary

Write

$n=\prod_{i=1}^k p_i^{e_i}.$

Every divisor of \(n\) is obtained by choosing exponents \(0\le a_i\le e_i\). The problem asks for the smallest positive integer \(n\) whose divisor structure has width at least \(10000\), where width means the size of the largest antichain in the divisibility order. The implementations never enumerate all divisors of large candidates directly; they work only with the exponent pattern of the prime factorization.

Mathematical Approach

Let \(W(n)\) denote the width of the divisor poset of \(n\). The central observation is that \(W(n)\) depends only on the multiset of exponents \(\{e_1,\dots,e_k\}\), so the search can be carried out on exponent sequences instead of on raw integers.

Step 1: View divisors as a product of chains

Each divisor has the form

$d=\prod_{i=1}^k p_i^{a_i},\qquad 0\le a_i\le e_i.$

For two divisors \(d=\prod p_i^{a_i}\) and \(m=\prod p_i^{b_i}\), divisibility is equivalent to coordinatewise comparison:

$d\mid m \iff a_i\le b_i\ \text{for all }i.$

Therefore the divisor poset is isomorphic to

$[0,e_1]\times[0,e_2]\times\cdots\times[0,e_k],$

a direct product of chains. This already shows that the actual prime values are irrelevant for the width; only the exponents matter.

Step 2: Convert width into a coefficient problem

Give the exponent vector \((a_1,\dots,a_k)\) the rank

$r(a_1,\dots,a_k)=a_1+\cdots+a_k.$

If two distinct vectors have the same rank, then neither can dominate the other coordinatewise, so every rank level is an antichain. A standard Sperner-type fact for products of chains says that a largest antichain is achieved by one of these levels. Hence \(W(n)\) is exactly the largest rank size.

Introduce the rank-generating polynomial

$P_n(x)=\prod_{i=1}^k (1+x+\cdots+x^{e_i})=\sum_{t=0}^{e_1+\cdots+e_k} c_t x^t.$

The coefficient \(c_t\) counts divisors whose exponent sum is \(t\). Therefore

$W(n)=\max_t c_t.$

Step 3: Compute \(W(n)\) by convolution

After processing exponents \(e_1,\dots,e_j\), let \(c^{(j)}_s\) be the number of ways to reach rank \(s\). Adding the next exponent \(e_{j+1}\) means multiplying by \(1+x+\cdots+x^{e_{j+1}}\), which gives the recurrence

$c^{(j+1)}_s=\sum_{t=0}^{e_{j+1}} c^{(j)}_{s-t}.$

So the width can be obtained by repeated coefficient convolution, starting from the one-term polynomial \(1\). When all factors have been processed, the largest entry of the resulting coefficient array is the width.

Step 4: Minimize the number for a fixed exponent multiset

For a fixed exponent multiset, the width is already determined, so the remaining task is to attach those exponents to primes as cheaply as possible. If \(p<q\) and \(a>b\), then

$p^a q^b < p^b q^a,$

because dividing the two sides gives \((p/q)^{a-b}<1\). Thus the smallest integer with exponents \(\{e_1,\dots,e_k\}\) is obtained by sorting them in nonincreasing order and assigning them to consecutive primes:

$n_{\min}(e_1,\dots,e_k)=2^{e_1}3^{e_2}5^{e_3}\cdots,\qquad e_1\ge e_2\ge\cdots\ge e_k\ge1.$

This turns the search into a search over nonincreasing exponent sequences.

Step 5: Depth-first search with branch-and-bound

The implementation explores exponent sequences \(e_1\ge e_2\ge\cdots\) by depth-first search. At each node it knows the current product and the current width obtained from the convolution above.

If the width has already reached \(10000\), the current product is a valid candidate and the branch can stop immediately, because appending more positive exponents would only multiply by extra prime powers and make the number larger.

If the current product is already at least as large as the best candidate found so far, that branch is pruned as well.

A useful initial upper bound comes from choosing sixteen distinct primes, which corresponds to exponent pattern

$\underbrace{(1,1,\dots,1)}_{16\text{ times}}.$

Then

$P_n(x)=(1+x)^{16},$

so the width is the central binomial coefficient

$\binom{16}{8}=12870>10000.$

Therefore the product of the first sixteen primes is a valid starting answer, giving the search a finite ceiling from the beginning.

Worked Example: \(n=5040\)

We have

$5040=2^4\cdot 3^2\cdot 5\cdot 7,$

so the exponent multiset is \((4,2,1,1)\). The rank-generating polynomial is

$P_{5040}(x)=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)^2.$

First multiply the last two factors:

$ (1+x+x^2)(1+x)^2 = 1+3x+4x^2+3x^3+x^4. $

Multiplying once more gives coefficient sequence

$1,\,4,\,8,\,11,\,12,\,11,\,8,\,4,\,1.$

The largest coefficient is \(12\), so

$W(5040)=12.$

Likewise, \(45=3^2\cdot5\) yields \((1+x+x^2)(1+x)=1+2x+2x^2+x^3\), hence \(W(45)=2\). These are the small verification values used by the implementations.

How the Code Works

The C++, Python, and Java implementations keep the current exponent sequence together with the current integer it represents. For each recursive state, they rebuild the coefficient array of \(P_n(x)\) by repeated convolution with short all-ones blocks and take the maximum coefficient as the current width.

The search always moves to the next prime and only tries exponents from \(1\) up to the previous exponent, which enforces the nonincreasing pattern proved above. Inside the loop, the next prime power is accumulated multiplicatively, so larger exponents reuse the work already done for smaller ones.

Whenever the target width is reached, the current product is compared with the best answer seen so far. Whenever the product itself has already grown past the best known candidate, the branch is abandoned. The C++ implementation uses 128-bit arithmetic for the running product, while the Python and Java implementations rely on arbitrary-precision integers.

Complexity Analysis

Consider a search state with exponent sequence \(e_1,\dots,e_k\) and total degree

$E=e_1+\cdots+e_k.$

Building the coefficient table for that state costs

$\Theta\!\left(\sum_{j=1}^k (E_{j-1}+1)(e_j+1)\right),\qquad E_{j-1}=e_1+\cdots+e_{j-1},$

which is \(O(E^2)\) in the worst case, and it uses \(O(E)\) memory for the current coefficient array.

If \(S\) is the set of visited search states, the total running time is

$O\!\left(\sum_{s\in S} E_s^2\right),$

where the practical size of \(S\) is controlled almost entirely by pruning. There is no simple closed form for the number of visited states, but the monotone exponent restriction and the explicit initial upper bound make the search small enough in practice.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=881
2. Generating functions: Wikipedia — Generating function
3. Divisors and divisor lattices: Wikipedia — Divisor
4. Sperner-type width results: Wikipedia — Sperner's theorem
5. Antichains and posets: Wikipedia — Partially ordered set