Exact bin packing the harmonic series: references?

Question

Given $n$ and $B_n= \lceil H_n \rceil$, where the latter is the $n$th harmonic number $\sum^n_{i=1} 1/i$, for most $n$ it is easy to pack the first $n$ terms of the harmonic series into $B_n$ many unit bins. An interesting question is for which $n$ one cannot perform such a packing. My guess is there are no such $n$, and I would like to know of references to this problem.

However, even more I would like to know about exact packing. There is no exact packing for $n=4$ or $5$, but (because $1= 1/2 + 1/3 + 1/6$) there are exact packings for other $n \leq 10$. Here a packing is exact if all but (at most) one bin is exactly filled to capacity.

What is the next $n \gt 10$ for which there is an exact packing?

Edit 2017.03.09 GRP: http://oeis.org/A101877 has more information. Call a subset $D$ of positive integers at most $n$ good for $n$ if the harmonic sum formed from $D$ Is floor of $H_n$. Hugo van der Sanden computed some of the good subsets below for $n=24,65,184$ and higher numbers, and Paul Hanna asked the stronger question if every subset good for $n$ had a subset good for (some number close to ) $n/e$. I am asking if there are some subsets good for enough $n$ that contain a chain of successively smaller subsets good for smaller integers so that an exact packing results. Ernie Croot III has shown (as told by Greg Martin in his ArXiv post on Denser Egyptian Fractions) a stronger result which implies that for all but finitely many integers $k$ there is an $n$ and a subset good for $n$ for which $k$ is floor of $H_n$. So far none of these references address the exact question asked above. (Double entendre intended.)

End Edit 2017.03.09 GRP.

Are there any references to this specific problem?

Gerhard "Not Going On A Trip" Paseman, 2017.01.25.

Answer 1

The next $n$ for which there is an exact packing are $24 \leq n \leq 30$. This is because $$ 1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = \frac{1}{4} + \frac{1}{5} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \frac{1}{15}+ \frac{1}{18} + \frac{1}{20} + \frac{1}{24}. $$ The sum of the remaining fractions is $< 1$ for $n$ in this range. Beyond this, the problem becomes quite intractable computationally.

Answer 2

Thanks to Jeremy Rouse, I have developed some heuristics and a nomogram-like approach to computing (bounds on a candidate for) the next smallest $n$ which admits an exact packing.

I call them heuristics, but they are modest extensions of known facts which should be easy to prove. The primary observation is that a prime power cannot occur just once in an integral packing, and if it occurs more than once, it must occur in a cancellative combination. Thus $1/25$ or $1/27$ can't be the only denominators in an integral packing with that high a power of $5$ or $3$, nor can we just have both of $1/25$ and $1/50$, but we can have $1/27$ and $1/54$ together, and we can have $1/50$ and $1/75$ together, or we can have any of the above with enough high powers of the same prime. This follows from looking at the $p$-adic value of $a/b + c/(dp^n)$ for $c$ and $d$ coprime to $p$ and $p^n$ not dividing $b$.

To help in determining which $n$ are feasible for an exact packing, I arrange the positive integers in several rows, with the $i$th row containing those numbers that are both multiples of the $i$th prime and have that prime as its largest prime factor. Part of the table looks like this with prime powers marked:

2  4*    8*              16*
  3   6    9*   12          18        24     27*
     5       10        15        20        25*        30
         7            14             21             28

I then use it to find a good subset of denominators, namely a set of integers at most $n$ whose reciprocal sum is $B_n - 1$. The bonus is that if this subset contains another which helps form an exact packing into $B_n - 2$ bins, then this good subset helps form an exact packing for $n$.

I can use this to find Jeremy Rouse's solution pretty quickly. As $H_{11}$ is near enough to $3 +1/11$, I first determine unfeasible $n\gt 11$ by noting that if $n\lt 18$, then $9$ cannot be part of a good subset,if $n \lt 24$ this excludes $8$, and if $n\lt 28$, then $7$ and its small multiples are excluded. Similarly, multiples of primes greater than 10 and prime powers greater than $10$ are excluded.

This leads to the conclusion that for $n\lt 18$ the sum of reciprocals of allowed numbers is less than $3$, and exceeds $3$ by $1/24$ only when $n=20$. When $n=24$ we get a potential good subset which excludes $12$ (because $12$ is needed to handle the excess) and Jeremy's solution pops out.

I can use the table also to determine quickly that after $30$, the next feasible number to admit an exact packing must be greater than $51$, primarily by balancing potential members greater than $31$ of a good subset against members less than $31$ which can't be part of a good subset for $n$: if the smaller denominators overpower the larger ones, then that $n$ is not feasible.

I then group the potential members by line, seeing if I can find subsets of each line which may be part of a good subset. Leaving out those found by Jeremy, for $n=66$ I find $16$ (contributing $1/16$), $12,27,36,48,54 (3/16)$, $30,60 (1/20),$ $7$ through $42 (7/20)$, $11,22,33,55,66 (1/5)$, and $13,26,52,65 (3/20)$, which gives an exact packing for $n=66$.

I have not determined if $65,63,$ or $60$ are feasible, but I suspect not as multiples of $17$ and higher primes are excluded already by $n \lt 68$, and the pair $55,66$ seems hard to replace. Note that these examples were found by hand, and that analysis of nice subsets of multiples of primes $p_i$ can be done programmatically. I disagree with Jeremy Rouse regarding the level of intractability of this problem, and thank him again for his inspiring example.

Edit 2017.03.06 GRP: After finding a packing for $n=65$ (leaving $ 21,39,44,$ and $55$ to handle the excess), I find that leaving out $65$ makes it impossible to produce an exact packing for $n=63$, as $13$ needs to be left out of the good subset, and so do a multiple of $7$ and a multiple of $11$, which is too much for the excess over $4$ of the smooth denominators that are candidates for a good packing. So after $30$, the next $n$ to admit an exact packing are $65$ through $82$.

Based on gut feel and some trial nomogramming, I suspect the next lowest admissible $n$ will be around $170$ or greater. So far the solutions above are found by hand. The exploration continues. End Edit 2017.03.06 GRP.

Gerhard "Who Wants To Go Further?" Paseman, 2017.03.03.

Answer 3

Here is the start of an approach which should lower the required ambition level of those willing to attempt a simulation.

Consider the denominator of $d_n=H_n - B_n+1$. The definition and theory show $1 \gt d_n \gt 0$ for $n \gt 1$, and so the denominator has a significant collection of prime factors. If the sum of reciprocals of those integers $i \leq n$ which "cover" the prime factors of the denominator is greater than $d_n$, then $n$ cannot admit an exact cover. By this reasoning one can show there is no exact cover for 11 through 14, and many larger $n$. I can see this heading toward a proof that there are only finitely many $n$ admitting an exact packing.

Edit: I should have thought this before posting. Apologies in advance, and thanks to any who can complete the argument.

I believe the denominator of $d_n$ contains all but a small fraction of the primes between $n^{1/2}$ and $n$. If this is so, then the sum of the reciprocals of a set of covering integers to include in a sum for $d_n$ is (by a theorem of Mertens or Euler) is going to be not much smaller than ln 2. Throw in powers of small primes and one sees that for large $n$ admitting an exact packing, $d_n$ has to be bigger than 2/3 and likely bigger than 1. This may leave a dearth of fractions to exactly fill the next to last bin.

Of course, the question of how many bins can be packed exactly arises. But let's wait for the first question to be resolved. End Edit.

Gerhard "Sorry For Not Thinking Earlier" Paseman, 2017.01.25.