Admin: Create Project Euler/110 page with problem statement, mathematical approach, branch-and-bound details, and solution link (via create-page on MediaWiki MCP Server)

2026-06-16T14:39:36Z

Create Project Euler/110 page with problem statement, mathematical approach, branch-and-bound details, and solution link (via create-page on MediaWiki MCP Server)

New page

==Problem Statement==

In the following equation <math>x</math>, <math>y</math>, and <math>n</math> are positive integers:

<math>
\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}
</math>

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

What is the least value of <math>n</math> for which the number of distinct solutions exceeds four million?

==Approach==

===Mathematical Reformulation===

The equation <math>\tfrac{1}{x} + \tfrac{1}{y} = \tfrac{1}{n}</math> can be rearranged algebraically:

<math>(x - n)(y - n) = n^2</math>

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

<math>
\text{solutions}(n) = \frac{d(n^2) + 1}{2}
</math>

where <math>d(k)</math> is the divisor-count function.

===Divisor Count of <math>n^2</math>===

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

<math>
d(n^2) = (2a_1 + 1)(2a_2 + 1) \cdots (2a_k + 1)
</math>

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

<math>d(n^2) \ge 8\,000\,001</math>

===Optimal Structure===

The least <math>n</math> achieving a given divisor count always uses the first <math>k</math> primes (<math>2, 3, 5, 7, 11, \dots</math>) 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 <math>n</math> while leaving <math>d(n^2)</math> unchanged.

===Branch-and-Bound Search===

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

* '''State:''' current prime index <math>i</math>, current exponent <math>e</math> (serving as upper bound for subsequent exponents), running product <math>n</math>, and running divisor-count product <math>d</math>.
* '''Branching:''' at each prime <math>p_i</math>, try exponents from the current maximum down to 1. Multiply <math>n</math> by <math>p_i^e</math> and multiply <math>d</math> by <math>(2e + 1)</math>.
* '''Upper bound for <math>n</math>:''' 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 <math>d</math> up to the target, the branch is abandoned.
* '''Overflow pruning:''' any <math>n</math> that already equals or exceeds the current <math>\text{bestN}</math> is skipped.

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

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

===Verification===

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

==Solution==

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

==Flags==

{{ProjectEulerFlag}}

Project Euler/110 - Revision history

Admin: Create Project Euler/110 page with problem statement, mathematical approach, branch-and-bound details, and solution link (via create-page on MediaWiki MCP Server)