The diophantine equation $ \sum_{n=1}^{N} \frac{1}{x_{n}} = \prod_{k=1}^{N} \left(1-\frac{1}{x_{k}} \right) $

Question

Background

I wonder if there are any rational numbers such that their Egyptian fraction (sum) representations are equal to their Egyptian product analogue. In other words, I am curious¹ about solutions to the diophantine equation

$$ \sum_{n=1}^{N} \frac{1}{x_{n}} = \prod_{k=1}^{N} \left(1-\frac{1}{x_{k}} \right) \tag{1}\label{1} $$

such that $x_{1} < x_{2} < \dots < x_{N-1} < x_{N} \in \mathbb{N}^{+}$ .

Solutions

Here are some solutions to equation \eqref{1} for small values of $N$:

• When $N=2$, the only solution appears to be $(x_{1},x_{2}) = (3,5) $, which yields the rational number $\frac{8}{15}$.
• For $N=3$, we have the solution $(x_1, x_2, x_3) = (3,6,28)$, yielding the rational number $\frac{15}{28}$.
• For $N=4$, I've found eight solutions so far. Let $x_{a}^{4}$ be the $a$'th solution of the equation in four variables. We then have $x_{1}^{4} = (3, 7, 24, 52)$, $x_{2}^{4} = (3, 9, 15, 37) $, $x_{3}^{4} = (3, 9, 16, 32)$, $x_{4}^{4} = (3, 10, 15, 26)$, $x_{5}^{4} = (4, 5, 15, 36)$, $x_{6}^{4} = (4,5,17,28)$, $x_{7}^{4} = (4,7,8,35)$, and $x_{8}^{4} = (5,6,10,12)$. These solutions correspond to the rational numbers $\frac{391}{728}$, $\frac{899}{1665}$, $\frac{155}{288}$, $\frac{7}{13}$, $\frac{49}{90}$, $\frac{324}{595}$, $\frac{153}{280}$, and $\frac{11}{20} $, respectively. User Max Alekseyev has found 24 solutions in total.
• As user Brendan Mckay pointed out, there are also solutions for the $N=5$ case. Denote $x_{a}^{5}$ as the $a$'th solution to the equation when $N=5$. Then we also have: $ x_{1}^{5} = (4,5,11,341,115820), x_{2}^{5} = (3,10,11,73, 37050)$, and $x_{3}^{5} = (3,9,11,458,209146) $. User David desJardins asserts that there are 293 solutions in total.
• User Max Alekseyev has found solutions when $N=6$ and $N=7$, including: $x_{1}^{6} = (3,7,27,50,336,1060) $ and $x_{1}^{7} = (3,7,13,15,16,35,96)$. He has also found solutions when $N=8, \dots , 13$.

User David desJardins obtains 9219 solutions when $N=6$, which he claims are all of them in this case.

According to user Cactus' answer to the MSE version of this question, there are finitely many solutions to this equation for all $N \geq 1$.

Related Equation

I know that in Znám's problem, solutions to the equation $$ \sum \frac{1}{x_{i}} + \prod \frac{1}{x_{i}} = y \tag{2}\label{2} $$ are studied, where $y$ and each $x_{i}$ must be integer. However, this equation is different from the one described above.

Questions:

1. Has equation \eqref{1} been described and studied in the mathematical literature before?
2. Are there any solutions for this diophantine equation for $N \geq 5$ ? If so, what are the respective solutions for the corresponding values of $N$, and how many are there?
3. Are there any solutions when $N \to \infty$ ?

---

^{1 I've asked another version of this question on MSE}

Answer 1

I can at any rate answer Q3: Yes, there are (plenty of) solutions for "N=infinity". And it will turn out that answering this in more detail resolves at least part of Q2: there is at least one solution for each positive N>1.

The "analytic process"

Start with the empty set of integers, yielding LHS=0 and RHS=1. Now repeatedly do the following: pick the smallest positive integer that (1) hasn't been used already and (2) preserves the condition LHS < RHS.

There always is such an integer, since large enough x will make the changes in LHS,RHS as small as you like. So the process goes on for ever.

The LHS is increasing and the RHS is decreasing. Any LHS value is a lower bound for all subsequent RHSes, and any RHS value is an upper bound for all subsequent LHSes. So the LHS and RHS are bounded monotone sequences and hence have limits.

I claim the limits are equal; if $R-L$ is bounded below by $\delta$ then any $n>1/\delta$ is acceptable for condition 2, so eventually we will use all such $n$ -- but these $n$ on their own are enough to make the LHS diverge to infinity and the RHS to zero, contradiction.

On the face of it this isn't a very explicit construction -- obviously you can just do it but it's not clear what the result looks like. But in fact it turns out we can understand it fairly well.

The "algebraic process"

Suppose at some stage we have partial sum $L$ and partial product $R$. The next $n$ will be the smallest integer bigger than $(R+1)/(R-L)$. Write $p=(R+1)/(R-L)$ and $q=1/(R-L)$. I claim that in fact $p,q$ are always integers!

(Note that this will also give us solutions for each $N$: take $n=p$ and the next $L,R$ will be equal.)

So, initially we have $L=0$ and $R=1$ so $p,q=2,1$: integers as required.

Now suppose $p,q$ are integers as claimed. We'll work out what happens next and see that the "next" values of $p,q$ are integers too. Specifically, let's begin by getting $L,R$ in terms of $p,q$: we have $L=(p-q-1)/q$ and $R=(p-q)/q$.

If $p,q$ are integers then our next $n$ is $p+1$, so we replace $L$ with $L'=L+1/(p+1)$ and $R$ with $R'=p/(p+1)\cdot R$. In terms of $p,q$ this turns out to mean $L'=(p^2-pq-1)/(p+1)q$ and $R'=(p^2-pq)/(p+1)q$.

This means $R'-L'=1/(p+1)q$ and so $p'=(R'+1)/(R'-L')=p^2+q$ and $q'=1/(R'-L')=(p+1)q$. And if $p,q$ are integers then so are $p',q'$.

So, to summarize:

• Write $p_1,q_1=2,1$ and $p_{n+1},q_{n+1}=p_n^2+q_n,(p_n+1)q_n$.
• We get a solution for "$n=\infty$" by taking our integers to be the $p_n+1$. We get a solution for any finite $n$ by taking an initial subsequence of the $p+1$ and then, finally, the next $p$.
• The resulting partial sum and product are $(p_n-q_n-1)/q_n$ and $(p_n-q_n)/q_n$.
• The differences RHS-LHS are $1/q_n$.
• The common limit of LHS and RHS (in the "$n=\infty$" case) is the limit of $p_n/q_n-1$.

Generalizing a bit

The things I've (rather dubiously) called "analytic" and "algebraic" are just two ways of looking at the exact same process, of course. But if we do something slightly different to one of them, it may have no equivalent in terms of the other.

Specifically, we can modify the "analytic" process so as to give (as promised at the start) "plenty of solutions" for $N=\infty$. Suppose we perform that process as described except that some finite number of times we pick a larger number than it asks for. Everything will still work, and we'll get an "$N=\infty$" solution, but it will no longer be describable in nice "algebraic" terms. This gives us countably infinitely many "$N=\infty$" solutions. If we want more, then (I think -- I haven't thought it through super-carefully) we can do the "analytic" process except that at each step we use either the number it asks for or the number 1 bigger, and again we will always get the LHS and RHS converging to a common value. So there are continuum-many solutions.

Alternatively, we could modify the "algebraic" process: start with some different $p_1,q_1$ and perform the calculations it calls for. This will give us different initial values of $L,R$, and the final result will have the property that $L+\sum 1/n=R\cdot\prod(1-1/n)$. This will not (except by some monstrous coincidence) be a solution to the original problem, but it might be of interest anyway; for instance, if we choose $p_1=3,q_1=2$ then we have $L=0,R=\frac12$, so this gives us a solution to $\sum 1/n=\frac12\prod(1-1/n)$.

Answer 2

For each $N$, you can enumerate all of the (finitely many) solutions, as follows.

Assume $x_1 < x_2 < \dots < x_N$. For each partial solution $(x_1,\dots,x_j)$, with $j < N$, let it be "viable" if both of these two conditions are met:

$$1/x_1+\cdots+1/x_j < (1-1/x_1)*\cdots*(1-1/x_j)$$

$$1/x_1+\cdots+1/x_j+1/(x_j+1)+\cdots+1/(x_j+N-j) \ge \\ (1-1/x_1)*\cdots*(1-1/x_j)*(1-1/(x_j+1))*\cdots*(1-1/(x_j+N-j))$$

For each viable $(x_1,\dots,x_j)$, there are only finitely many $x_{j+1}>x_j$ such that $(x_1,\dots,x_j,x_{j+1})$ is viable. So, start with the empty partial solution $()$, and enumerate all of the viable partial solutions as a tree. Then, for each viable $(x_1,\dots,x_{N-1})$, check whether there is an integer $x_N$ that creates a full solution.

This algorithm is fast enough to enumerate the 293 solutions for $N=5$ almost instantly, and the 9219 solutions for $N=6$ in several minutes. It's probably not feasible for $N=7$ without some further optimization.

Answer 3

A short answer related to OP's Q3, derived from Gareth's answer and my comments: Define the (characteristic) polynomial of the sequence $x=\{x_1,...,x_N\}$, $$ \tag{1}\label{eq:1} P_{x}(\xi)=\prod_{k=1}^N(x_k-\xi) \, . $$ Then, OP's (1) ist equivalent to $$ \tag{2}\label{eq:2} \frac{P_{x}(1)}{P_{x}(0)} + \frac{P_{x}'(0)}{P_{x}(0)} = 0 \quad\Leftrightarrow\quad P_{x}(1) + P_{x}'(0) = 0 \, . $$ Denote the minimal (smallest $x_k$) infinite solution constructed with Gareth's algorithm $$ \tag{3}\label{eq:3} x^\mathrm{min} = (3, 6, 29, 803, 643727, 414383582243, 171713753231982206218247, \ldots) \, . $$ It defines a family of polynomials (I'll drop the superscript min) $$ \tag{4}\label{eq:4} p_n(\xi) = \prod_{k=1}^n(x^\mathrm{min}_k - \xi) $$ that fulfill $$ \tag{5}\label{eq:5} p_n(1) + p_n'(0) = 1 $$ for all $n \in \mathbb{N}^{+}$ and even for $n=0$, if we define the empty product to be one as usual.

From \eqref{eq:5} we can construct a recursion relation for $p_n(\xi)$, as $$ \tag{6}\label{eq:6} p_{n}(1)(x_{n+1}-1) + p_{n}'(0) x_{n+1} - p_{n}(0) = 1 \, , $$ such that $$ \tag{7}\label{eq:7} x_{n+1} = \frac{p_{n}(1) + p_{n}(0) + 1}{p_{n}(1)+p_{n}'(0)} \stackrel{\eqref{eq:5}}{=} p_{n}(1) + p_{n}(0) + 1 \, . $$ The recursion becomes $$ \tag{8}\label{eq:8} p_0(\xi)=1 \, , \qquad \frac{p_{n+1}(\xi)}{p_{n}(\xi)} = p_{n}(1) + p_{n}(0) + 1 - \xi \, . $$ The common limit of sum and product is given by $$ \lim_{n\to\infty}\frac{p_{n}(1)}{p_{n}(0)} = 0.53572964208911646\ldots \, . $$

Answer 4

I've posted all 787,444 solutions for $N=7$ at this link.

To compute these solutions, I've used bounds similar to those proposed in the answer by David desJardins, but only for terms $x_1, \dots, x_{N-2}$. The remaining two terms satisfy the equation: $$\frac{a}{c}+\frac{1}{x_{N-1}}+\frac{1}{x_N} = \frac{b}{c} \big(1-\frac1{x_{N-1}}\big)\big(1-\frac1{x_N}\big),$$ where $\frac{a}{c} := \sum_{i=1}^{N-2} \frac1{x_i}$, $\frac{b}{c} := \prod_{i=1}^{N-2} (1-\frac1{x_i})$, and $\gcd(a,b,c)=1$, which is equivalent to $$\big((a-b) x_{N-1} + b+c\big)\cdot \big((a-b) x_N + b+c\big) = b(a-b) + (b+c)^2$$ from where the suitable values of $x_{N-1}$ and $x_N$ can be determined efficiently by factoring of the right hand side.

---

I've also added solution counts to the OEIS as sequence A369469. A similar sequence A369470 enumerates solutions with possibly equal terms.

Answer 5

Uniqueness for $N<4$:

Related to Q1, we have simple proofs for a limited number of solutions when $N=2$ or $N=3$. The given solution for $N=2$ is unique. The one in the question for $N=3$ is unique only if we require all variables to be strictly distinct.

$N=2$

Expanding the product and collecting like tetms gives

$1-\dfrac2{x_1}-\dfrac2{x_2}+\dfrac2{x_1x_2}=0$

Clearing fractions and movibg the cobstant term to the right:

$x_1x_2-2x_1-2x_2=-1$

Add $4$ to each side anf the left side can now be factored:

$x_1x_2-2x_1-2x_2+4=(x_1-2)(x_2-2)=3$

As $3$ is prime, the only positive solution then requires the factors on the left to be $1,3$. This allows only the solution $\{x_1,x_2\}=\{3,5\}$.

$N=3$

In this case expanding the product and clearing fractions gives

$1-\dfrac2{x_1}-\dfrac2{x_2}-\dfrac2{x_3}+\dfrac1{x_1x_2}+\dfrac1{x_1x_3}+\dfrac1{x_2x_3}+\dfrac1{x_1x_2x_3}=0$

Clear fractions and add the linear and constant terms to render the left side factorable:

$x_1x_2x_3-2(x_1x_2+x_1x_3+x_2x_3)+4(x_1+x_2+x_3)-8=(x_1-2)(x_2-2)(x_3-2)=3(x_1+x_2+x_3)-9$ Eq. 1

Now suppose wlog that $x_1<x_2<x_3$. Then

$(x_1-2)(x_2-3)<\dfrac{9x_3-9}{x_3-2}\le18,$

where we use the fact that in positive solutions all elements must be at least $3$. Strictly speaking the upper bound could be reduced to $12$ (with $x_3\ge5$) if the variables are truly distinct, but if we allow equal values ($x_1\le x_2\le x_3, x_3\ge 3$) then we would need to consider products up to $18$. We shall see that this distinction has a difference later on.

We then have a limited number of trials for which $x_2>x_1\ge3$ and $(x_1)(x_2)\le18$. To run these trials each candidate ordered pair is plugged in for $(x_1,x_2)$ and Equation 1 solved for $x_3$. This gives one solution for $N=3$:

$(x_1,x_2,x_3)=(3,6,28)$

as specified in the question, if all values are distinct. However, if we were to allow repeated values then the additional trials would give a second solution:

$(x_1,x_2,x_3)=(4,4,25)$

The rational fraction value for this repeated solution is $27/50$. Note the minimal value is constrained to be $\le5$ in either case, matching the solutions for higher $N$.

Infinite Sequences: A less greedy algorithm

Turning to Q3, we know now that there are infinite sequence solutions. But can we get a sequence that grows more slowly than Fred Hucht's? Such an alternative is desirable because we would avoid numbers blowing up for longer, thus generating a more pleasing sequence and allowing more calculations with standard computing tools.

Suppose we have $k$ terms of such a strictly increasing sequence, namely $x_1,x_2,...,x_k$. To define $x_{k+1}$ we form the equation

$\sum\limits_{n=1}^k\dfrac1{x_k}+\dfrac1{m}+\dfrac1{s}=\left(\prod\limits_{n=1}^k\left(1-\dfrac1{x_n}\right)\right)\left(1-\dfrac1{m}\right)\left(1-\dfrac1{s}\right),$ Eq. 2

where $m$ is a whole number greater than $x_k$ and $s$ is a not necessarily whole number for which Eq. 2 becomes exact. For different whole numbers $m$ we find that $s$ is a decreasing function of $m$ and that there is a maximal value of $m$ for which $s$ remains greater than or equal to that $m$. Our definition of $x_{k+1}$ will be that maximal value of $m$.

For instance, if we start with $x_1=3$ then $m=6$ gives $s=28$ as we have seen, but $m=9$ gives $s=10.75>9$ versus $m=10$ giving $s=9.6<10$. So the next term after $3$ would be $9$ and we can generate the sequence

$3,9,21,43,86,172,345,693,1387,2774,5548,...$

giving a converged value for the sum/product of about $0.538$. Although the second number in the sequence is greater than that in Fred's ($9$ versus $6$), the next numbers are much smaller with this algorithm as if in a reverse tortoise-vs-hare race.

If we start with $x_1=4$ we get

$4,6,15,31,63,128,259,520,1042,2084,4170,...$

with a converged sum/product of about $0.547$.

Note the near-geometric sequences in both cases above.