Sum of Egyptian Fractions

Posted: July 23, 2012 | Author: evouga | Filed under: Random Math | Leave a comment »

A friend recently posed me the following question: for an integer $n$, how many pairs of positive integers $(a,b)$ exist for which

$$\frac{1}{n} = \frac{1}{a} + \frac{1}{b}?$$

Call this number $F(n)$. Here is my solution. We will count the number of positive integers $a$ for which there exists a corresponding $b$.

First, note that a $b$ exists if and only if the numerator of $\frac{a-n}{an}$ cancels when the fraction is put into lowest terms, in other words, if and only if $a-n\vert an$.

 

Lemma 1: $F(n)$ is equal to the number of integers $a>n$ for which $a-n \vert (a,n)^2$, where $(a,n)$ denotes the greatest common divisor of $a$ and $n$.

To see this fact, write $a = x(a,n)$ and $b = y(a,n)$. Then $(x-y) \vert x y (a,n)$. Since $x$ and $y$ are relatively prime, $x-y$ is relatively prime to both $x$ and $y$, so $(x-y)\vert (a,n)$, or $(a-n)\vert (a,n)^2.$

 

Lemma 2: $F(n)$ is equal to the number of integers $a>n$ for which $a-n \vert n^2$.

We will show that this set of $a$s and the set of $a$s given by Lemma 1 are in bijection. First, if $a-n\vert (a,n)^2$, then clearly $a-n\vert n^2$ since $(a,n)$ is a divisor of $n$.

Now suppose $(a-n)\vert n^2$. Then $a-n$ is equal to a divisor $d$ of $n^2$. We can write $d=d_1d_2$ where $d_1\vert n$ and $d_2 \vert n$. Therefore both $d_1$ and $d_2$ divide the right-hand side and so divide $a$, so both are common divisors of $a$ and $n$ and so $d_1\vert (a,n)$ and $d_2 \vert (a,n)$. Therefore $d_1d_2 \vert (a,n)^2$.

Since for every divisor of $n^2$ we can solve for a unique $a>n$, we have

 

Answer: $F(n) = d(n^2)$, where the divisor function $d(x)$ counts the number of positive divisors of $x$. Note that this $F$ counts unordered pairs. There are $\frac{d(n^2)+1}{2}$ unique ordered pairs with $a \leq b$. For $n=10^7$, there are 225 pairs (113 ordered pairs).

$d(n^2)$ can be computed naively in $O(n)$ by finding $n$'s prime factorization using trial division. Possibly there are faster algorithms.

 

Footnote: Like the divisor function, $F$ is multiplicative: if $(x,y) = 1$, $F(xy) = F(x)F(y)$. Maybe there's a way to see that directly and use it to derive a formula for $F$ in an alternate way (by first finding a formula for $F(n)$ when $n$ is a prime power.)

---