Detailed mathematical approach

Problem Summary

Let \(f(n)\) be the number of positive-integer solutions of

$\frac{1}{a}+\frac{1}{b}=\frac{p}{10^n}.$

The Project Euler task is to compute \(\sum_{n=1}^{9} f(n)\). The variable \(p\) is part of the solution rather than an input, so the real difficulty is to understand which pairs \((a,b)\) can occur and how many values of \(p\) they generate.

A direct search is not realistic because \(a\) and \(b\) are not bounded in advance. The key simplification is to separate the common factor of \(a\) and \(b\), reduce the problem to a coprime core, and then count all lifts of that core through the divisor function.

Mathematical Approach

The entire solution turns on one observation: once the common factor of \(a\) and \(b\) is removed, the remaining coprime pieces can only involve the primes 2 and 5, because the right-hand side has denominator \(10^n=2^n5^n\).

Strip off the gcd

Write

$a=dx,\qquad b=dy,\qquad \gcd(x,y)=1.$

Substituting into the equation gives

$\frac{1}{dx}+\frac{1}{dy}=\frac{x+y}{dxy}=\frac{p}{10^n},$

so after clearing denominators we get

$10^n(x+y)=pdxy.$

For a fixed coprime pair \((x,y)\), all remaining freedom is carried by the common factor \(d\) and the numerator \(p\).

Why the reduced denominators must divide \(10^n\)

If a prime divides both \(xy\) and \(x+y\), then it divides one of \(x\) or \(y\), and therefore also the other, contradicting \(\gcd(x,y)=1\). Hence

$\gcd(xy,x+y)=1.$

From

$10^n(x+y)=pdxy$

it follows that every prime factor of \(xy\) must already come from \(10^n\). Therefore

$xy\mid 10^n,$

so \(x\) and \(y\) can only use the primes 2 and 5. We may write

$x=2^u5^v,\qquad y=2^r5^s,$

with

$u+r\le n,\qquad v+s\le n,\qquad \min(u,r)=0,\qquad \min(v,s)=0.$

The last two conditions express the coprimality of \(x\) and \(y\): for each prime, all of its exponent sits on one side or the other, never both.

Canonical reduced pairs

The equation is symmetric in \(a\) and \(b\), so after reducing to \((x,y)\) we only need one canonical ordering for the coprime pair. Because only the primes 2 and 5 are available, every reduced pair falls into one of two families:

$\bigl(1,2^\alpha5^\beta\bigr)\quad\text{with}\quad 0\le \alpha,\beta\le n,$

or

$\bigl(2^\alpha,5^\beta\bigr)\quad\text{with}\quad 1\le \alpha,\beta\le n.$

The first family covers the case where one reduced denominator receives both prime powers, and the second family covers the split case where one side is a pure power of 2 and the other is a pure power of 5. This is exactly the symmetry reduction encoded by the implementations.

Each reduced pair contributes a divisor count

Rearrange the main equation as

$pd=\frac{10^n(x+y)}{xy}=(x+y)2^{\,n-u-r}5^{\,n-v-s}=:K.$

Now fix a valid coprime pair \((x,y)\). If \(d\) is any positive divisor of \(K\), then

$a=dx,\qquad b=dy,\qquad p=\frac{K}{d}$

gives a positive-integer solution. Conversely, every solution with this reduced pair must satisfy \(d\mid K\). So the number of solutions arising from one canonical pair \((x,y)\) is exactly

$\tau(K),$

where \(\tau\) is the divisor-counting function. The whole problem is therefore reduced to enumerating the canonical coprime pairs and summing \(\tau(K)\).

Worked Example: \(n=1\)

For \(n=1\), the canonical reduced pairs are

$ (1,1),\ (1,2),\ (1,5),\ (1,10),\ (2,5). $

The corresponding values of \(K\) are

$ 20,\ 15,\ 12,\ 11,\ 7, $

so their contributions are

$ \tau(20)=6,\quad \tau(15)=4,\quad \tau(12)=6,\quad \tau(11)=2,\quad \tau(7)=2. $

Adding them gives

$f(1)=6+4+6+2+2=20,$

which matches the published checkpoint. The divisor interpretation is concrete here: for the reduced pair \((x,y)=(1,1)\), we have \(K=20\), and every divisor \(d\) of 20 produces a solution \((a,b,p)=(d,d,20/d)\).

How the Code Works

The C++, Python, and Java implementations never search over \(a\), \(b\), or \(p\) directly. They iterate over the exponents of 2 and 5 that define the canonical reduced pair, compute the corresponding value of \(K\), and add its number of divisors.

Enumerating the canonical exponent patterns

One exponent of 2 is pinned to zero from the start, which forces a unique orientation whenever one reduced denominator carries a factor of 2. If neither side carries a factor of 2, one exponent of 5 is also pinned to zero, removing the remaining swap symmetry. In effect, this loop structure enumerates exactly the two mathematical families \(\bigl(1,2^\alpha5^\beta\bigr)\) and \(\bigl(2^\alpha,5^\beta\bigr)\) without duplicates.

Turning one candidate into a contribution

For each exponent tuple, the implementation reconstructs the two reduced denominators, forms the scaling factor \(2^{n-u-r}5^{n-v-s}\), and evaluates

$K=(x+y)2^{\,n-u-r}5^{\,n-v-s}.$

It then factors \(K\) by trial division and converts the prime exponents into \(\tau(K)\). That value is added to the running total for the current \(n\), and the outer loop sums the counts for \(n=1\) through \(9\). The C++ and Python implementations also verify the published checkpoint \(f(1)=20\) before printing the final total.

Complexity Analysis

For a fixed \(n\), the canonical pairs are easy to count: there are \((n+1)^2\) pairs of the form \(\bigl(1,2^\alpha5^\beta\bigr)\) and \(n^2\) pairs of the form \(\bigl(2^\alpha,5^\beta\bigr)\). So the enumeration cost is \(O(n^2)\) candidates per \(n\).

For each candidate, the implementations factor \(K\) by trial division, which costs \(O(\sqrt{K})\) in the worst case. In this problem \(K\) is at most on the order of \(10^n\), and the Euler target only needs \(n\le 9\), so the numeric work is tiny in practice. Memory usage is \(O(1)\), because only a handful of integers are stored at any moment.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=157
2. Diophantine equation: Wikipedia - Diophantine equation
3. Divisor function: Wikipedia - Divisor function
4. Greatest common divisor: Wikipedia - Greatest common divisor
5. Fundamental theorem of arithmetic: Wikipedia - Fundamental theorem of arithmetic