Diophantine equation: Egyptian fraction representations of 1 - MathOverflow

Diophantine equation: Egyptian fraction representations of 1

2010-06-12T03:11:55Z

According to the OEIS (A002966) there are 294314 solutions in positive integers to the equation $$\sum_{i=1}^7\frac{1}{x_i}=1$$ assuming $x_1\leq x_2\leq\cdots\leq x_7$.
Similarly for 8 summands there are 159330691 solutions.

My question: What are they? Is there a way of counting them without knowing them?

The bound for $x_n$ for $n$ summands is double exponential and I could only compute the solutions up to $n=6$ with Maple.

Answer by David Eppstein for Diophantine equation: Egyptian fraction representations of 1

2010-06-12T07:14:16Z

160 million is not a lot to list exhaustively by computer as long as the time is reasonably fast for each one.

I think the standard way to solve this sort of problem is a backtracking search that tries all possibilities for x1, then x2, etc. The constraints that $x_i\ge x_{i-1}$ and that $\frac{n-i+1}{x_i}\ge 1-\sum_{j=1}^{i-1}x_j$ mean that one only has to try finitely many possibilities for $x_i$ at each step.

Answer by Hugo van der Sanden for Diophantine equation: Egyptian fraction representations of 1

2010-06-12T10:29:52Z

As far as I know, the only significant result to speed up these calculations is that $E_2(\frac{p}{q}) = \frac{1}{2}|\lbrace d: d | q^2, d \equiv -q (mod p) \rbrace|$, where $E_2(p/q)$ represents the number of decompositions into 2 unit fractions, and each matching $d$ represents the decomposition $\frac{p}{q} = \frac{qp}{q(q+d)} + \frac{dp}{q(q+d)}$. (Take floor() or ceil() depending on whether you want to allow repeats.)

When I've coded this in the past, I called one of 4 different functions depending on a) whether $p=1$ or not, and b) whether $q/p \ge min$ or not, where $min$ is the greatest denominator I'm already using. When $p=1$ and $q \ge min$, in particular, we can just calculate $\tau(q^2)/2$ from the factorisation of $q$; in the other cases I actually walked the factors from $q/p$ to $\sqrt{q}$.

So: yes, you can count the number of matching sets without generating the 7 elements of each set, but computationally the elements are just a whisker away.

Answer by Marc LeBrun for Diophantine equation: Egyptian fraction representations of 1

2012-05-08T06:55:14Z

A related interesting problem is the number of partitions of 1 into n distinct positive Egyptian fractions, the first few terms of which are given in A006585.

These values were counted laboriously by brute force in the early 1990's, and although they have been reconfirmed (by Jud McCranie) the sequence has only been extended one further term (by John Dethridge) in 2004.

Additional terms, cleverer algorithms and/or a generating function, would be most welcome!