Problem 157: Solving the Equation 1/a + 1/b = p / 10^n

Mathematical Analysis

Key Transformation

Let $N = 10^n$. From $\frac{1}{a} + \frac{1}{b} = \frac{p}{N}$:

Rearranging and completing the product:

Multiply by $p$ and add $N^2$:

Enumeration via Divisors

Let $u = pa - N$ and $v = pb - N$ with $uv = N^2 = 10^{2n}$.

Claim: Both $u$ and $v$ must be positive.

Proof: Since $a, b, p > 0$, we need $pa > 0$ and $pb > 0$. If $u < 0$ and $v < 0$, then $|u| < N$ and $|v| < N$, giving $|u||v| < N^2$, contradicting $uv = N^2$. If one is positive and one negative, $uv < 0 \ne N^2$. So both are positive.

For each divisor $u$ of $N^2$ with $1 \le u \le N$ (ensuring $u \le v$, which gives $a \le b$):

1. Set $v = N^2 / u$.
2. Compute $g = \gcd(N + u, N + v)$.
3. Each divisor $p$ of $g$ yields a valid solution: $a = (N+u)/p$, $b = (N+v)/p$.
4. Since $a \le b$ requires $u \le v$ (already ensured), and $a, b$ are positive integers when $p | \gcd(N+u, N+v)$, the contribution from this divisor pair is $\tau(g)$, the number of positive divisors of $g$.

Proof of Correctness

Given a divisor pair $(u, v)$ with $uv = N^2$, and any positive divisor $p$ of $\gcd(N+u, N+v)$:

• $a = (N+u)/p$ and $b = (N+v)/p$ are positive integers.
• $(pa - N)(pb - N) = uv = N^2$, which expands to $N(a+b) = pab$.
• Hence $\frac{1}{a} + \frac{1}{b} = \frac{p}{N}$ with $a \le b$.
• Conversely, every solution $(a, b, p)$ arises this way.

Why divisors of $10^{2n}$ suffice

$N^2 = 10^{2n} = 2^{2n} \cdot 5^{2n}$. Its divisors are exactly the numbers $2^i \cdot 5^j$ with $0 \le i, j \le 2n$. The number of divisors is $(2n+1)^2$.

Counting formula

Per-$n$ breakdown

Complexity

The number of divisors of $10^{2n}$ is $(2n+1)^2$. For each divisor pair, we compute a GCD ($O(\log N)$) and count divisors ($O(\sqrt{g})$). Total work is negligible.

Answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Count number of positive divisors of n
int count_divisors(ll n) {
    if (n <= 0) return 0;
    int count = 0;
    for (ll d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            count++;
            if (d != n / d) count++;
        }
    }
    return count;
}

// Get all divisors of 10^(2n) = 2^(2n) * 5^(2n)
vector<ll> get_divisors(int n2) {
    vector<ll> divs;
    for (int a = 0; a <= n2; a++) {
        for (int b = 0; b <= n2; b++) {
            ll d = 1;
            for (int i = 0; i < a; i++) d *= 2;
            for (int i = 0; i < b; i++) d *= 5;
            divs.push_back(d);
        }
    }
    sort(divs.begin(), divs.end());
    return divs;
}

int main() {
    ll total = 0;
    for (int n = 1; n <= 9; n++) {
        ll N = 1;
        for (int i = 0; i < n; i++) N *= 10;
        ll N2 = N * N;
        vector<ll> divs = get_divisors(2 * n);
        for (ll u : divs) {
            if (u > N) continue; // u <= N ensures a <= b
            ll v = N2 / u;
            ll g = __gcd(N + u, N + v);
            total += count_divisors(g);
        }
    }
    cout << total << endl;
    return 0;
}

from math import gcd

def count_divisors(n):
    """Count the number of positive divisors of n."""
    if n <= 0:
        return 0
    count = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            count += 1
            if d != n // d:
                count += 1
        d += 1
    return count

def get_divisors(n2):
    """Get all divisors of 10^n2 = 2^n2 * 5^n2."""
    divs = []
    for a in range(n2 + 1):
        for b in range(n2 + 1):
            divs.append(2**a * 5**b)
    return sorted(divs)

total = 0
for n in range(1, 10):
    N = 10**n
    N2 = N * N
    divs = get_divisors(2 * n)
    subtotal = 0
    for u in divs:
        if u > N:
            continue  # ensures a <= b
        v = N2 // u
        g = gcd(N + u, N + v)
        subtotal += count_divisors(g)
    total += subtotal

print(total)