14
$\begingroup$

Let $N(m)$ be the max of $n$ such that $\sum_{i=1}^n\frac{1}{a_i}=1$ where $a_i \ (i=1,2,\cdots,n)$ are integers which satisfy $2\le a_1\lt a_2\lt\cdots\lt a_n\le m$.

Question 1 : What is $N(99)$?

Question 2 : What is $N(m)$?

Examples : I'm going to represent $\sum_{i=1}^n\frac{1}{a_i}$ as $(a_1,a_2,\cdots,a_n).$

The followings are two examples for $(m,n)=(99,42)$.

$(15,17,20,21,22,26,27,30,32,33,34,35,36,38,39,40,42,44,45,48,50,52,54,55,56,60, 63,66,70,75,76,77,78,80,84,85,88,90,91,95,96,99)$
$(17,18,20,21,22,24,26,27,32,33,34,35,36,38,39,40,42,44,45,48,50,52,54,55,56,60,63,66,70,72,75,76,77,78,80,84,85,88,91,95,96,99)$

Remark :

Question 1 has been asked on math.SE.

https://math.stackexchange.com/questions/488173/what-is-the-max-of-n-such-that-sum-i-1n-frac1a-i-1-where-2-le-a-1-l

$99$ has no special meaning except that $99$ is not too small and not too large.

Question 2 might be somewhat ambiguous. The best answer would be to represent $N(m)$ by $m$ if it is possible. Also, finding both the max of $m$ and the min of $m$ would be needed.

Motivation : The beginning was the following:

"$\sum_{k=2}^n \frac 1k$ is not an integer for any $n$."

(the proof and the other related facts can be seen at https://math.stackexchange.com/questions/494174/proving-that-the-finite-sum-of-the-each-reciprocal-of-any-sequence-of-integers-w).

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ Why the number 99? $\endgroup$
    – Boris Bukh
    Commented Sep 16, 2013 at 14:58
  • 14
    $\begingroup$ Why 4 votes to close in 40 minutes? Can 4 people solve it or write a computer program that solves it in reasonable time already? If so, I feel quite retarded compared to those guys... $\endgroup$
    – fedja
    Commented Sep 16, 2013 at 15:22
  • 10
    $\begingroup$ As with many other problems here (and elsewhere in research mathematics), even if the question itself is of only recreational interest, still the analytical and computational techniques can be of wider interest. Voted to reopen. $\endgroup$
    – Noam D. Elkies
    Commented Sep 16, 2013 at 17:50
  • 17
    $\begingroup$ My opinion is that the good etiquette is that if you see no value in the question for yourself, you just ignore it. If you close something as "having no research value", it means that the question is beneath you and you have a good reason to believe that it is beneath other people here as well (i.e., you can solve it in a few minutes and tell the sketch of a solution in a few lines). I merely do not believe in any other abstract "value" of research or of life, much less in the ability of anybody to evaluate this value at the first glance in non-obvious cases. Voting to reopen :-). $\endgroup$
    – fedja
    Commented Sep 16, 2013 at 18:33
  • 2
    $\begingroup$ I agree with @fedja that the question should not have been closed. I also feel that the question with $99$ replaced by $m$ would be more interesting. After all, for $m$ very small the question is trivial; and I cannot tell where the "border of triviality" lies. $\endgroup$
    – Boris Bukh
    Commented Sep 16, 2013 at 21:06

3 Answers 3

Reset to default
17
$\begingroup$

Note that $N(m)$ cannot be significantly larger than $m(1-1/e)$, since the sum of the reciprocals of any $m(1-1/e)$ integers not exceeding $m$ is at least $\sum_{m/e < k < m} 1/k \sim 1$.

I've proved that in fact, $N(m)$ is asymptotic to $m(1-1/e)$; in other words, you can have essentially as many summands as size considerations allow you to have. See Theorem 1 and equation (5) of my paper "Denser Eygptian fractions". (There I consider the equivalent dual problem - instead of fixing $m$ and trying to maximize the number of summands, I fix the number of summands and try to minimize $m$.)

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ Thanks for the link! Is anyone still insisting that this puzzle is not "research level"? :-) $\endgroup$
    – fedja
    Commented Sep 17, 2013 at 12:56
8
$\begingroup$

Answered on mathstackexchange: the upper bound of $99$ turns out to be small enough for complete enumeration by dynamical programming after accounting for small primes and prime powers; the maximum is indeed $42$, attained in $27$ ways, which I'll be able to list after some more computing.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Did you mean a different question number? MO142348 is a deleted question. (or is the first part of the challenge figuring out what you meant?...) $\endgroup$
    – Noam D. Elkies
    Commented Sep 17, 2013 at 0:49
  • $\begingroup$ I see that you already deleted your own first comment, without which the rest of this thread makes no sense. Shall we delete it all then? $\endgroup$
    – Noam D. Elkies
    Commented Sep 17, 2013 at 1:03
  • $\begingroup$ Now updated the stackexchange answer to include the full list. $\endgroup$
    – Noam D. Elkies
    Commented Sep 17, 2013 at 5:09
4
$\begingroup$

Noting that the answers with many components involve few primes, I assume that any answer involves no primes (or denominators with prime factors) greater than 36. The sum of 1/i from m to n can be estimated as roughly log(n) - log(m-1), so no answer will contain all the numbers from (about) 36 to 99, and indeed the numbers from 27 to 99 minus all the numbers with prime factors over 36 will overshoot the target of 1, so an upper bound of 55 is easily estimated. If it can be proved that numbers under 20 are part of the answer, this bound of 55 can be easily reduced. (In fact, one can prove no primes greater than 19 are involved, which brings an upper bound down to around 48.)

Gerhard "Still Getting Used To 2.0" Paseman, 2013.09.16

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .