Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
It would be interesting if the solutions can be counted without computing them. If $\pi(x)$ can be computed, maybe so can this. –  Dror Speiser Jun 12 '10 at 8:42
1  
Quite non-standard in diophantine business to count such an enormous amount of solutions: one usually have very few... :-) There is a related diophantine equation, the so-called unit fraction equation, $$ \sum_{i=1}^k\frac1{x_i}+\prod_{i=1}^k\frac1{x_i}=1, $$ for which some work was done (but it's far from being complete), see [W. Butske et al, Comput. Math. 69 (1999), no. 229, 407--420]. –  Wadim Zudilin Jun 12 '10 at 11:23
    
Wadim, here is more recent paper on this type of equations: arxiv.org/abs/0712.3954 –  Max Alekseyev Jul 2 '10 at 1:05
add comment

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
Thanks! I really want the actual solutions and I was worried that the count was obtained in a significantly faster way. If I understand one would have to follow Eppstein's approach to get down to determining $x_1$ and $x_2$ and then one can count. I guess I should try to get some time on my university's supercomputer! –  Eric Rowell Jun 12 '10 at 16:18
    
It should be $d\equiv -q\pmod{p}$, not $d\equiv -p\pmod{p}$. Basically, the underling trick here is that $$\frac{1}{u}+\frac{1}{u} = \frac{p}{q}$$ is reduced to a certain factorization of $q^2$: $$(pu-q)(pv-q) = q^2.$$ Assuming that the terms of expansion are sorted as $x_1 < x_2 < \dots < x_n$, they are typically generated from low-index to high-index and the above trick is used after the values to $x_1,\dots,x_{n-2}$ were assigned to quickly determine the values of $u=x_{n-1}$ and $v=x_n$ with $$\frac{p}{q} = 1 - \frac{1}{x_1} - \dots - \frac{1}{x_{n-2}}.$$ –  Max Alekseyev Jun 30 '10 at 0:02
    
@Max: thanks, I've corrected it to -q (mod p). –  Hugo van der Sanden Jun 30 '10 at 8:31
add comment

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.

share|improve this answer
    
What is the best data structure for storing the intermediate data and the answer? –  Victor Protsak Jun 12 '10 at 7:32
    
David, the computational strategy is clear. But the OP seems to be how to count the number of solutions without ctual computing them. At least how to estimate the asymptotics of the counting sequence. –  Wadim Zudilin Jun 12 '10 at 14:05
    
This is how I did the $n=6$ case. Unfortunately the bound on $x_1$ for $n=7$ is already around $10^13$. Moreover the bound is attained! So I guess the issue is storage as was suggested. For my application I actually want the solutions but I wasn't sure if the counts on OEIS were obtained without the actual solutions. –  Eric Rowell Jun 12 '10 at 16:11
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.