Project Euler/110

Problem Statement

In the following equation $ x $, $ y $, and $ n $ are positive integers:

$ \dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n} $

It can be verified that when $ n = 1260 $ there are 113 distinct solutions and this is the least value of $ n $ for which the total number of distinct solutions exceeds one hundred.

What is the least value of $ n $ for which the number of distinct solutions exceeds four million?

Approach

Mathematical Reformulation

The equation $ \tfrac{1}{x} + \tfrac{1}{y} = \tfrac{1}{n} $ can be rearranged algebraically:

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

Each divisor pair $ (d, n^2/d) $ of $ n^2 $ yields a distinct ordered solution $ (x, y) $. Because the equation is symmetric in $ x $ and $ y $, the number of distinct unordered solutions is:

$ \text{solutions}(n) = \frac{d(n^2) + 1}{2} $

where $ d(k) $ is the divisor-count function.

Divisor Count of $ n^2 $

If $ n $ has prime factorization $ n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} $, then:

$ d(n^2) = (2a_1 + 1)(2a_2 + 1) \cdots (2a_k + 1) $

The target condition $ \text{solutions}(n) > 4\,000\,000 $ is equivalent to:

$ d(n^2) \ge 8\,000\,001 $

Optimal Structure

The least $ n $ achieving a given divisor count always uses the first $ k $ primes ($ 2, 3, 5, 7, 11, \dots $) with exponents in non-increasing order — the largest exponents are assigned to the smallest primes. This is because swapping exponents between a larger and smaller prime would increase $ n $ while leaving $ d(n^2) $ unchanged.

Branch-and-Bound Search

We search over exponent vectors using depth-first branch-and-bound:

• State: current prime index $ i $, current exponent $ e $ (serving as upper bound for subsequent exponents), running product $ n $, and running divisor-count product $ d $.
• Branching: at each prime $ p_i $, try exponents from the current maximum down to 1. Multiply $ n $ by $ p_i^e $ and multiply $ d $ by $ (2e + 1) $.
• Upper bound for $ n $: use consecutive primes each with exponent 1 as an initial best; any branch exceeding this value is pruned.
• Feasibility pruning: if the remaining primes — even at the current exponent (the maximum allowed) — cannot multiply $ d $ up to the target, the branch is abandoned.
• Overflow pruning: any $ n $ that already equals or exceeds the current $ \text{bestN} $ is skipped.

When $ d \ge 8\,000\,001 $, the candidate $ n $ is recorded if it improves upon the best found.

Fifteen primes suffice because $ 3^{15} = 14\,348\,907 > 8\,000\,001 $, covering the worst case where every exponent is 1.

Verification

The solution code includes built-in verification: it computes the number of solutions for $ n = 1260 $ (confirming 113) and finds the least $ n $ with over 100 solutions (confirming 1260).

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem110.java