Diophantine equation: Egyptian fraction representations of 1 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T12:19:12Z http://mathoverflow.net/feeds/question/27896 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1 Diophantine equation: Egyptian fraction representations of 1 Eric Rowell 2010-06-12T03:11:55Z 2012-05-08T06:55:14Z <p>According to the OEIS (<a href="http://www.research.att.com/~njas/sequences/A002966" rel="nofollow">A002966</a>) 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$.<br> Similarly for 8 summands there are 159330691 solutions.</p> <p>My question: What are they? Is there a way of counting them without knowing them?</p> <p>The bound for $x_n$ for $n$ summands is double exponential and I could only compute the solutions up to $n=6$ with Maple.</p> http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1/27911#27911 Answer by David Eppstein for Diophantine equation: Egyptian fraction representations of 1 David Eppstein 2010-06-12T07:14:16Z 2010-06-12T07:14:16Z <p>160 million is not a lot to list exhaustively by computer as long as the time is reasonably fast for each one.</p> <p>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.</p> http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1/27925#27925 Answer by Hugo van der Sanden for Diophantine equation: Egyptian fraction representations of 1 Hugo van der Sanden 2010-06-12T10:29:52Z 2010-06-30T08:30:55Z <p>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.)</p> <p>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}$.</p> <p>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.</p> http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1/96302#96302 Answer by Marc LeBrun for Diophantine equation: Egyptian fraction representations of 1 Marc LeBrun 2012-05-08T06:55:14Z 2012-05-08T06:55:14Z <p>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.</p> <p>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.</p> <p>Additional terms, cleverer algorithms and/or a generating function, would be most welcome!</p>