22

Which natural number can be represented as a product of a sum of natural numbers and a sum of their inverses? I. e. does there exist for a natural $n$ a set of natural numbers $\{a_1, a_2,...a_m\}$ such that $n = (a_1 + a_2 + ...+a_m)(\frac{1}{a_1} + \frac{1}{a_2} + ... +\frac{1}{a_m})$? Call $n$ good if such a set exists, they do not have to be distinct.

All $n = k^2$ are good, if n is good then $2n + 2$ is good as well, 10 and 11 are good, 2,3,5,6,7,8 are not. I'm too lazy to check any further especially if there is a solution out there, please point me if you know one.

Does there exist a constant $C$ such that all $n \geq C$ are good? What if I let $a_i$s to be negative?

Now mathoverflow gave me a link to another question Estimating the size of solutions of a diophantine equation which gives 14 as a good number (hard). Moreover there is a link to a very nice paper "An Unusual Cubic Representation Problem" by Andrew Bremner and Allan MacLeod which gives a whole bunch of solutions already for $m = 3$ on page 38 here http://ami.ektf.hu/uploads/papers/finalpdf/AMI_43_from29to41.pdf, for all their $N$ we get $2(N + 3)$ to be good. So if we take $C = 30$, then all even $N \geq C$ are good (needs a clear proof).

Question There is still question about what happens for odd $N$s. And maybe it's worthy to ask if we can restrict $m$. I. e. What is the smallest $k$ such that any good $N$ can be represented as a product above with $k \geq m$?

Darya Schedrina
  • 223

4 Answers4

29

Graham (1963) proved that any integer $n>77$ can be represented as $$ n = a_1 + \dots + a_m,$$ where $a_i$ are distinct positive integers with $$\frac{1}{a_1} + \dots + \frac{1}{a_m} = 1.$$ Hence, any integer $n>77$ is good.

Btw, I've recently extended the result of Graham to sums of squares.

UPDATE. As for the largest non-good (bad?) number, we know that $8$ is not good, while OEIS A028229 leaves just seven more candidates for the largest non-good number: $12, 13, 14, 15, 19, 21$, or $23$.

Numbers $14, 15, 19, 21, 23$ are good with the corresponding $\{ a_i\}$ being $\{ 2, 3, 10\}$, $\{1, 2, 6\}$, $\{ 5, 8, 12, 15\}$, $\{ 8, 14, 15, 35\}$, and $\{76, 220, 285, 385\}$, respectively.

Hence, there remains just 3 candidate for the largest non-good number: $8, 12$, or $13$. While the latter two candidates can be good only with $m=3$, MacLeod's approach (Sec. 6.2) here leads to elliptic curves of zero rank, thus implying that both $12$ and $13$ are not good.

Therefore, $13$ is the largest non-good number.

Max Alekseyev
  • 30,425
19

A note on the observation "$n$ good implies $2n + 2$ good":

First remark is that $n$ is good iff there are positive rational numbers $a_1, \dotsc, a_m$ such that $n = (a_1 + \dotsc + a_m)(1/a_1 + \dotsc + 1 / a_m)$. This is because one can multiply all $a_i$ by the lcm of their denominators.

Second remark is that $n$ is good iff there are positive rational numbers such that $n = 1/a_1 + \dotsc + 1/a_m$ and $a_1 + \dotsc + a_m = 1$. This is because one can multiply all $a_i$ by the inverse of their sum.

Finally, if $n = 1/a_1 + \dotsc + 1/a_m$ with $a_1 + \dotsc + a_m = 1$, then taking $a_i' = a_i / 2$ for $1\leq i \leq m$ and $a_{m + 1}' = 1/2$ gives us $2n + 2$.

Looking at the proof by Graham cited above, I see that this observation is indeed halfway to the actual proof. Namely we need a second result that $n$ good implies $2n + 179$ good, to take care of the odd integers. Then the result follows from the fact that all integers from $78$ to $333$ are good.

Since we don't require the $a_i$'s to be different, we may take $a_i' = a_i / 2$ for $1 \leq i \leq m$, $a_{m + 1}' = 1/3$, $a_{m + 2}' = 1/6$, and get $2n + 9$ good.

This also suggests that we might improve significantly the bound of Graham.

Following the comment of Max Alekseyev, this OEIS sequence says that all positive integers except $2, 3, 5, 6, 7, 8, 12, 13, 14, 15, 19, 21, 23$ are Egyptian, and hence good.

Since our definition of "good" is weaker than "Egyptian", it doesn't a priori exclude the possibility that some of the above listed numbers are still good.

Therefore it only remains to see whether the above numbers are good.

The task is separated into $m = 2, 3, 4$.

For $m = 2$, it is clear that only for $n = 4$, the equation $(x + y)(1/x + 1/y) = n$ has rational solution $(x, y)$.

For $m = 3$, we are led to the equation $(x + y + z)(xy + yz + zx) = nxyz$. Assuming $n > 9$ and choosing the point $[x, y, z] = [-1, 1, 0]$ as the point at infinity, we get an elliptic curve.

A Weierstrass equation is given by $Y^2 = X^3 + (n^2 - 6n - 3)X^2 + 16nX$, where $X = \frac{4n(x + y)}{x + y - (n - 1)z}$, $Y = \frac{4n(n - 1)(x - y)}{x + y - (n - 1)z}$. To get back $[x, y, z]$ from $X, Y$, we have the formula $[x, y, z] = [(n - 1)X + Y, (n - 1)X - Y, 2X - 8n]$.

This curve has six torsion points, which correspond to useless solutions to our equation. Moreover, the Mordell-Weil group has rank $0$ for all the above $n$, except $n = 14, 15$. This proves that $n = 12, 13$ are not good.

For $n = 14$, we have a solution $(3, 10, 15)$.

For $n = 15$, we have a solution $(1, 3, 6)$.

Thanks again to Max Alekseyev, $n = 19, 21, 23$ are all good, with solutions $(5,8,12,15), (8,14,15,35), (76,220,285,385)$, respectively.

Conclusion: A positive integer is good if and only if it is not one of $2, 3, 5, 6, 7, 8, 12, 13$.

WhatsUp
  • 3,232
  • 16
  • 22
  • How do you get this: $n$ good, then $2n + 179$ good? Thanks! – Darya Schedrina Dec 01 '19 at 18:36
  • 1
    This comes from the paper of Graham. Under our notation here: $1/3 + 1/7 + 1/78 + 1/91 + a_1/2 + \dotsc + a_m/2 = 1$, and hence $3 + 7 + 78 + 91 + 2n = 2n + 179$ is good. Note that Graham needs all $a_i$ to be different, so for us it's enough to have e.g. $1/3 + 1/6 + a_1/2 + \dotsc + a_m/2 = 1$ and hence $2n + 9$ is good. – WhatsUp Dec 01 '19 at 18:41
  • 1
    OEIS A028229 implies that all $n>23$ are good. – Max Alekseyev Dec 01 '19 at 18:53
  • Strictly speaking, OEIS A028229 is not the result of Graham. Also, you gave a link to the same paper of him. – Max Alekseyev Dec 01 '19 at 22:12
  • @MaxAlekseyev Ah... thanks for pointing out. You see, I simply copied that link from the OEIS page without looking into the details. The OEIS page is kind of misleading, by putting the link to Graham's paper under "The table of n, a(n)". – WhatsUp Dec 01 '19 at 22:36
  • user44191's comment shows that $2,3,5,6,7,8$ are not good. This leaves only $12,13,14,15,19,21,23$ unknown, with the first four requiring checking $m$ up to $3$ and the last three $m$ up to $4$. – Will Sawin Dec 02 '19 at 00:19
  • @WillSawin Checking $m = 3$ is easy, because these are elliptic curves. But I still don't see how to do it efficiently for $m = 4$, that's why I didn't update the answer. It seems plaussible to me that a map from a surface to a curve should be "almost surjective", but that's just my very vague intuition. – WhatsUp Dec 02 '19 at 00:26
  • @WhatsUp I think that depends a lot on which surface and which curve (and, in particular, what is the genus of the fibers). – Will Sawin Dec 02 '19 at 00:34
  • @WillSawin It turns out that the $m = 4$ case is not a huge problem here, because solutions are found by Max Alekseyev! We now have a complete answer. – WhatsUp Dec 02 '19 at 02:22
4

You can find an infinite number of good numbers $n$. You can use the formula $$\frac{1}{\frac{2!}{1}}+\frac{1}{\frac{3!}{2}}+\frac{1}{\frac{4!}{3}}+...+\frac{1}{\frac{m!}{m-1}}+\frac{1}{m!}=1$$ and deduce that $n=(2!/1+3!/2+...+m!/(m-1)+m!)(\frac{1}{\frac{2!}{1}}+\frac{1}{\frac{3!}{2}}+\frac{1}{\frac{4!}{3}}+...+\frac{1}{\frac{m!}{m-1}}+\frac{1}{m!})$ is obviously good.

Konstantinos Gaitanas
  • 3,826
  • 1
    I'm afraid you misunderstood the question. – WhatsUp Dec 01 '19 at 17:29
  • It is just a partial solution. Not a complete answer, obviously. But a solution for any desired number of summands. – Konstantinos Gaitanas Dec 01 '19 at 17:32
  • 1
    Then wouldn't all $a_i=1$ be a simpler example? – WhatsUp Dec 01 '19 at 17:43
  • Yes, but the case where $a_i=1$ is already mentioned ($n=k^2$ is good...) – Konstantinos Gaitanas Dec 01 '19 at 17:57
  • 3
    I think you're misleading people by saying "You can find a solution for every $m$". The problem is of the form "Is it true that for every $n$ there is a solution to ...?" The question has nothing to do with how large or small $m$ can be. So you'll make it easier on the reader if you edit you answer to start something like: "I do not know how to find a solution for all (sufficiently large) $n$, but here is an interesting identity that gives some examples of $n$ that work." – Joe Silverman Dec 01 '19 at 18:04
  • @ joe silverman I made an edit. – Konstantinos Gaitanas Dec 01 '19 at 18:13
3

Any $n$ which is of the form $4P$ where $P$ is a perfect number is good: just consider as a set $\{a_{i}\}$ the set of its divisors. As the sum of the reciprocals thereof equals $2$, this guarantees that your product is an integer, hence that $n$ is good.

Sylvain JULIEN
  • 6,960