14
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ It would be interesting if the solutions can be counted without computing them. If $\pi(x)$ can be computed, maybe so can this. $\endgroup$
    – Dror Speiser
    Jun 12, 2010 at 8:42
  • 2
    $\begingroup$ 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]. $\endgroup$
    – Wadim Zudilin
    Jun 12, 2010 at 11:23
  • $\begingroup$ Wadim, here is more recent paper on this type of equations: arxiv.org/abs/0712.3954 $\endgroup$
    – Max Alekseyev
    Jul 2, 2010 at 1:05

3 Answers 3

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Eric Rowell
    Jun 12, 2010 at 16:18
  • $\begingroup$ 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}}.$$ $\endgroup$
    – Max Alekseyev
    Jun 30, 2010 at 0:02
  • $\begingroup$ @Max: thanks, I've corrected it to -q (mod p). $\endgroup$
    – Hugo van der Sanden
    Jun 30, 2010 at 8:31
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What is the best data structure for storing the intermediate data and the answer? $\endgroup$
    – Victor Protsak
    Jun 12, 2010 at 7:32
  • $\begingroup$ 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. $\endgroup$
    – Wadim Zudilin
    Jun 12, 2010 at 14:05
  • $\begingroup$ 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. $\endgroup$
    – Eric Rowell
    Jun 12, 2010 at 16:11
2
$\begingroup$

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!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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