# 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.

• For the computationally ambitious, a reasonable approach is to look at $H_n - B_n + 1$, and see if it is a subsum of the (properly truncated) harmonic series. If this fails for $n \gt 10$, then there is no larger $n$ which admits an exact packing. Gerhard "Not Feeling Computationally Ambitious Today" Paseman, 2017.01.25. – Gerhard Paseman Jan 25 '17 at 18:40
• What does it mean "packing into x many unit bins"? Please, give a definition. – user40023 Jan 27 '17 at 20:11
• Given a set of n objects with weights x_i for i from 1 to n, a packing into K many unit bins is a partition into K pieces of the index set such that for each piece P_k , the sum of x_i as i ranges over the members of P_k is at most 1, for each of the K pieces P_k. An exact packing has the sum exactly 1 for each piece. I can pack the n weights 1/i into n unit bins, and probably into about 1+log n many unit bins, but for n > 1, I can't do an exact packing because H_n is not an integer. The question above asks if I can get very close. Gerhard "Sort Of Exact, Not Exactly" Paseman, 2017.01.27 – Gerhard Paseman Jan 27 '17 at 23:40
• Based on the exact packing for n=66 (which extends through to n=82), it seems reasonable that for every value of $B_n$ there will be an $n$ which admits an exact packing. This means that my conjecture above (every $n$ admits a packing into $B_n$ bins) holds conditionally. Gerhard "Don't Use Induction In Shower" Paseman, 2017.03.03. – Gerhard Paseman Mar 3 '17 at 19:04

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.

• Wow! I didn't think you could find this! Dare to conjecture if there are any more, or how soon we can exactly pack the next bin? Gerhard "Go On, I Dare You" Paseman, 2017.02.28. – Gerhard Paseman Feb 28 '17 at 20:21
• Also, you have quite a few smooth numbers as denominators. Perhaps an estimate as to how many sevenses or elevenses are needed may give a clue? Gerhard "Happy Birthday To My Dad" Paseman, 2017.02.28. – Gerhard Paseman Feb 28 '17 at 20:25
• If you are sufficiently computationally ambitious, here is what may be a tractable subtask. Given n and E_n = B_n - 1, the number of bins to pack exactly, let G_p be the subset of unit fractions with p smooth denominators. Bump up p until the sum over G_p exceeds E_n, and then see if the difference is expressible as a sum of a subset of G_p. When it is, you have a trial set for exact packing, or possibly a short proof that it can't be done. Gerhard "May Compute Ambitiously Later Today" Paseman, 2017.02.28. – Gerhard Paseman Feb 28 '17 at 20:42
• This gets a vote up from me. Gerhard "That Might Be My Tenth" Paseman, 2017.03.03. – Gerhard Paseman Mar 3 '17 at 18:49

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.

• This problem has a tie-in with abundant and multiperfect numbers. If we can find a small enough number $m$ with high abundance ratio $r$, that might lead to finding a divisor $n$ of $m$ which admits an exact packing of $B_n =$ ceiling($r$) bins. For example, $m=360$ being abundant leads to Jeremy's example. Gerhard "Oh, The Connections To Make!" Paseman, 2017.03.03. – Gerhard Paseman Mar 3 '17 at 18:17
• We have $\frac{1}{21} + \frac{1}{55} + \frac{1}{66}= \frac{1}{40} + \frac{1}{45} + \frac{1}{56} + \frac{1}{63}$, so we can modify the packing for $n=66$ to get one for $n=65$. On to $63$. Gerhard "Still Making Examples By Hand" Paseman, 2017.03.05. – Gerhard Paseman Mar 6 '17 at 1:55

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.

• The edit to the above post contains some muddled thinking. Once enough multiples (let's say $k=\log p$ many) of a prime $p$ are included below $n$, it is reasonable that a sum of some of the reciprocals adds to a fraction whose denominator divides $k!$, and thus contributes to a good subset as given in the other answers. Thus not very many numbers are left out of a good subset, and it may be that it suffices for an exact packing to have the fractional part of $H_n$ exceed something like $3/4$. Gerhard "How's That For A Conjecture?" Paseman, 2017.03.03. – Gerhard Paseman Mar 3 '17 at 18:40