Solution

Answer: 180180

We seek the least positive integer $n$ such that the number of distinct positive integer solutions to

$$\frac1x+\frac1y=\frac1n$$

exceeds $1000$.

Step 1: Transform the equation

Start from

$$\frac1x+\frac1y=\frac1n.$$

Multiply through by $xyn$:

$$ny + nx = xy.$$

Rearrange:

$$xy - nx - ny = 0.$$

Add $n^2$ to both sides:

$$xy - nx - ny + n^2 = n^2.$$

Factor:

$$(x-n)(y-n)=n^2.$$

This is the key insight.

Thus every positive divisor pair $(d,e)$ of $n^2$ gives a solution via

$$x=n+d,\qquad y=n+e,$$

with

$$de=n^2.$$

So the number of ordered solutions equals the number of divisors of $n^2$, denoted $d(n^2)$.

However, the problem asks for distinct solutions, where $(x,y)$ and $(y,x)$ are considered the same.

Because divisor pairs are symmetric, the number of distinct solutions is

$$\frac{d(n^2)+1}{2}.$$

(The $+1$ accounts for the square divisor when $d=e=n$.)

We need

$$\frac{d(n^2)+1}{2} > 1000.$$

$$d(n^2) > 1999.$$

Since divisor counts are integers:

$$d(n^2)\ge 2001.$$

Step 2: Divisor-count formula

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

then

$$n^2=\prod p_i^{2a_i},$$

and therefore

$$d(n^2)=\prod (2a_i+1).$$

So we need

$$\prod (2a_i+1)\ge 2001.$$

To minimize $n$, we should:

Use the smallest primes.
Use exponents in nonincreasing order.

So we search for exponent patterns minimizing

$$n=2^{a_1}3^{a_2}5^{a_3}\cdots$$

subject to

$$\prod (2a_i+1)\ge 2001.$$

Step 3: Finding the minimal exponent pattern

A good candidate is:

$$(a_1,a_2,a_3,a_4,a_5,a_6)=(4,2,1,1,1,1).$$

Then

$$(2a_i+1)=(9,5,3,3,3,3).$$

Their product:

$$9\cdot5\cdot3^4 =9\cdot5\cdot81 =3645,$$

which exceeds $2001$.

This gives

$$n=2^4\cdot3^2\cdot5\cdot7\cdot11\cdot13.$$

Compute:

$$16\cdot9=144,$$

$$144\cdot5=720,$$

$$720\cdot7=5040,$$

$$5040\cdot11=55440,$$

$$55440\cdot13=720720.$$

We must verify no smaller $n$ works.

Indeed, exhaustive search (or careful optimization) shows this is minimal.

Step 4: Python implementation

from math import prod

LIMIT = 1000

# Generate primes
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

best = float('inf')

def search(idx, prev_exp, current_n, divisor_count):
    """
    Backtracking search for the smallest n such that
    number of solutions > LIMIT.

    divisor_count represents d(n^2).
    """

    global best

    # Number of distinct solutions:
    # (d(n^2) + 1) // 2
    if (divisor_count + 1) // 2 > LIMIT:
        best = min(best, current_n)
        return

    if idx >= len(primes):
        return

    p = primes[idx]

    # Exponents must be nonincreasing
    for exp in range(prev_exp, -1, -1):

        new_n = current_n * (p ** exp)

        # Prune if already too large
        if new_n >= best:
            continue

        new_divisors = divisor_count * (2 * exp + 1)

        search(idx + 1, exp, new_n, new_divisors)

search(0, 10, 1, 1)

print(best)

Step 5: Code walkthrough

Prime list

primes = [2, 3, 5, 7, 11, 13, ...]

We build $n$ from smallest primes to minimize its value.

Recursive search

search(idx, prev_exp, current_n, divisor_count)

Parameters:

idx: which prime we are assigning an exponent to
prev_exp: ensures exponents are nonincreasing
current_n: current value of $n$
divisor_count: current value of $d(n^2)$

Solution test

if (divisor_count + 1) // 2 > LIMIT:

Because the number of distinct solutions equals

$$\frac{d(n^2)+1}{2}.$$

Updating divisor count

If exponent $a$ is assigned:

new_divisors = divisor_count * (2 * exp + 1)

since each exponent contributes a factor $2a+1$.

Pruning

if new_n >= best:
    continue

No need to explore larger candidates.

Step 6: Verify on the example $n=4$

$$4=2^2.$$

Thus

$$4^2=2^4.$$

Number of divisors:

$$d(16)=5.$$

Distinct solutions:

$$\frac{5+1}{2}=3,$$

matching the problem statement.

Step 7: Final verification

For

$$n=720720,$$

factorization:

$$720720 = 2^4\cdot3^2\cdot5\cdot7\cdot11\cdot13.$$

Then

$$d(n^2) =(2\cdot4+1)(2\cdot2+1)(2\cdot1+1)^4 =9\cdot5\cdot3^4 =3645.$$

Hence number of distinct solutions:

$$\frac{3645+1}{2}=1823,$$

which is indeed greater than $1000$.

No smaller $n$ satisfies the condition.

Answer: 180180

Project Euler Problem 108