Skip to main content
4 of 4
added 864 characters in body
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Exact bin packing the harmonic series: references?

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.

Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63