Solution

Answer: 205702861096933200

Let

$$n=\prod_{i=1}^r p_i^{a_i}$$

with distinct primes $p_i$ and exponents $a_i\ge 1$.

We are asked to study the graph on the divisors of $n$:

vertices = divisors of $n$,
edge $a\to b$ if $a<b$ and $b/a$ is prime.

The graph is layered by distance from $n$, and $g(n)$ is the largest layer size.

We want the smallest $n$ such that

$$g(n)\ge 10^4.$$

1. Mathematical analysis

Step 1 — Encode divisors by exponent vectors

Every divisor of $n$ has the form

$$d=\prod p_i^{e_i}, \qquad 0\le e_i\le a_i.$$

An edge corresponds to multiplying/dividing by exactly one prime, i.e. changing exactly one exponent by $1$.

Starting from $n$, whose exponent vector is

$$(a_1,a_2,\dots,a_r),$$

moving one edge downward decreases one coordinate by $1$.

Therefore the distance from $n$ to divisor $d$ is

$$\sum_{i=1}^r (a_i-e_i).$$

So the vertices at level $k$ are exactly those divisors satisfying

$$\sum (a_i-e_i)=k.$$

Equivalently, define

$$b_i=a_i-e_i,\qquad 0\le b_i\le a_i.$$

Then the number of vertices at level $k$ equals the number of solutions of

$$b_1+b_2+\cdots+b_r=k, \qquad 0\le b_i\le a_i.$$

That is precisely the coefficient of $x^k$ in

$$\prod_{i=1}^r (1+x+\cdots+x^{a_i}).$$

Hence:

$$g(n)=\max_k [x^k]\prod_{i=1}^r (1+x+\cdots+x^{a_i}).$$

Step 2 — The optimization problem

The primes themselves do not affect $g(n)$; only the exponent multiset matters.

To minimize $n$, once the exponents are fixed, we should assign the largest exponents to the smallest primes:

$$a_1\ge a_2\ge \cdots$$

paired with

$$2,3,5,7,\dots$$

because of the rearrangement inequality.

Thus the problem becomes:

Find nonincreasing exponents $a_1\ge a_2\ge\cdots\ge0$ such that

$$\max_k [x^k]\prod (1+x+\cdots+x^{a_i})\ge 10^4,$$

while minimizing

$$n=\prod p_i^{a_i}.$$

Step 3 — Efficient search

For a candidate exponent list $(a_1,\dots,a_r)$:

compute the polynomial coefficients by dynamic programming,
take the maximum coefficient,
recursively search exponent patterns in nonincreasing order,
prune whenever the current number already exceeds the best found.

This search is very small because:

coefficients grow quickly,
the optimal exponents are tiny.

The optimal exponent pattern turns out to be

$$(4,3,2,2,2,1,1,1,1,1,1,1).$$

Thus

$$n = 2^4\cdot3^3\cdot5^2\cdot7^2\cdot11^2 \cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37.$$

The corresponding maximal coefficient is

$$10130>10000.$$

2. Python implementation

from functools import lru_cache

TARGET = 10_000

# Enough small primes for the optimal solution
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]

best_n = float('inf')
best_exp = None

@lru_cache(None)
def max_level_size(exponents):
    """
    Return the maximum coefficient of

        ∏ (1 + x + ... + x^a)

    where exponents = (a1, a2, ...).
    """

    poly = [1]

    for a in exponents:
        new_poly = [0] * (len(poly) + a)

        for i, c in enumerate(poly):
            for j in range(a + 1):
                new_poly[i + j] += c

        poly = new_poly

    return max(poly)

def dfs(index, last_exp, current_n, exponents):
    """
    Depth-first search over nonincreasing exponent sequences.
    """

    global best_n, best_exp

    # Current g(n)
    g = max_level_size(tuple(exponents))

    # Success
    if g >= TARGET:
        if current_n < best_n:
            best_n = current_n
            best_exp = exponents.copy()
        return

    # No more primes available
    if index >= len(PRIMES):
        return

    # Prune
    if current_n >= best_n:
        return

    p = PRIMES[index]
    power = 1

    # Exponents must be nonincreasing
    for e in range(1, last_exp + 1):
        power *= p
        new_n = current_n * power

        if new_n >= best_n:
            break

        exponents.append(e)

        dfs(index + 1, e, new_n, exponents)

        exponents.pop()

dfs(0, 20, 1, [])

print("Best n =", best_n)
print("Exponents =", best_exp)
print("g(n) =", max_level_size(tuple(best_exp)))

3. Code walkthrough

`max_level_size`

We build the generating polynomial

$$\prod (1+x+\cdots+x^{a_i})$$

coefficient-by-coefficient.

Example:

For exponents $(2,1)$,

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

Hence $g(n)=2$.

DFS search

We recursively build exponent lists:

exponents are forced to be nonincreasing,
exponent $e_i$ is attached to the $i$-th prime,
we stop if the current $n$ already exceeds the best known answer.

Verification on the example $n=45$

$$45 = 3^2 \cdot 5^1.$$

So the polynomial is

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

Largest coefficient:

$$g(45)=2,$$

matching the statement.

Verification on $n=5040$

$$5040=2^4\cdot3^2\cdot5\cdot7.$$

Polynomial:

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

Its largest coefficient is $12$, matching the problem statement.

4. Final verification

The optimal exponent pattern found is

$$(4,3,2,2,2,1,1,1,1,1,1,1),$$

giving

$$g(n)=10130.$$

Any smaller exponent configuration either:

produces $g(n)<10000$, or
yields a larger number after assigning exponents optimally to primes.

Thus the minimum is

$$n= 2^4\cdot3^3\cdot5^2\cdot7^2\cdot11^2 \cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37.$$

Multiplying out:

$$n=205702861096933200.$$

Answer: 205702861096933200

Project Euler Problem 881