For positive integers $n\_1, \ldots, n\_k$, let $H(n\_1, \ldots, n\_k)$ denote $1/n\_1 + \ldots + 1/n\_k$. Let $V(N)$ be the largest possible value of $H(n\_1, \ldots, n\_k)$ that is less than 1, subject to the condition that $n\_1 + \ldots +n\_k \le N$. So $V(5) = 5/6$, realized as $1/2 + 1/3$. My question is, how does $1/(1-V(N))$ grow as a function of $N$? In particular, is there a $C$ and a $k$ such that 
$$
\frac 1{1-V(N)} \le C N^k\
$$
for all $N$?



Representing a number close to 1 with a sum of reciprocals of natural numbers
$K(N) := 1 / (1 - V(N))$ grows faster than any power of $N$.


This can be seen by finding for each $k$ an identity
$$
\sum\_{i=1}^m \frac{A\_i x + B\_i}{C\_i x + D\_i}
 = 1 - c x^{-(2k+1)} + O(x^{-(2k+2)})
$$
where the coefficients $A\_i,B\_i,C\_i,D\_i$ are integers
with $A\_i, C\_i > 0$ and $c$ is a positive rational number
(and the right-hand side is a Taylor expansion about $x=\infty$).
Once we have such an identity, we can take for $x$ a large integer
(in particular large enough that the denominators $C\_i x + D\_i$
and numerators $A\_i x + B\_i$ are all positive), and write each term
$(A\_i x + B\_i) \, / \, (C\_i x + D\_i)$ as a sum of $A\_i x + B\_i$ copies of
the reciprocal of $C\_i x + D\_i$. Then as $x\rightarrow\infty$
the sum $N$ of the denominators grows as a multiple of $x^2$,
while $1/(1-H)$ grows as $x^{2k+1}$ which is faster than $N^k$.


The identity we need is easy to construct because the conditions
on the coefficients are linear in the $B\_i$ (and also in the $A\_i$,
but we do not use this). For example, fix distinct rationals $\delta\_i$
and positive rationals $\alpha\_i$ with $\sum\_{i=1}^m \alpha\_i = 1$,
and then find rational $\beta\_i$ such that
$$
\sum\_{i=1}^m \frac{\alpha\_i x + \beta\_i}{x + \delta\_i} = 1 + O(x^{-(2k+1)});
$$
that's $2k$ independent linear equations in $m$ unknowns,
so there exists a solution once $m \geq 2k$. Then write
each term $(\alpha\_i x + \beta\_i) / (x + \delta\_i)$ 
as $(A\_i x + B\_i) \, / \, (C\_i x + D\_i)$ with integer coefficients.
We must show that there is a choice of $\alpha\_i$ and $\delta\_i$
that makes the $x^{-(2k+1)}$ coefficient nonzero; but this is easy,
for example because otherwise that coefficient would vanish identically,
even if we allowed complex $\alpha\_i$ and $\delta\_i$, and that's
contradicted (for $m=2k+1$) by the partial-fraction decomposition
of the rational function $X^{2k+1} / (X^{2k+1} - 1)$. **Jeremy Kahn**
insists that the $x^{-(2k+1)}$ coefficient be negative, but if our
recipe happens to yield a positive coefficient then we can get a
negative one by changing each $B\_i$ and $D\_i$ to $-B\_i$ and $-D\_i$
respectively (that's why we used an odd exponent $2k+1$).


It may be reasonable to expect that $K(N)$ grows almost as fast
as the number of partitions $(n\_1,\ldots,n\_k)$ of $N$, i.e.
$\log K(N)$ should be asymptotic to some multiple of $\sqrt{N}$
(or at any rate it should grow not much slower than $\sqrt{N})$,
because there are plenty of partitions for which $\sum\_{i=1}^k 1/n\_i < 1$.
Numerical computation seems to corroborate this guess; here are the record
values of $K(N)$ for $2 \leq N \leq 72$, followed by the total number of
partitions and the count of partitions with $\sum\_{i=1}^k 1/n\_i < 1$:



```
 N     K(N)        #      #1
 2      2          2       2
 5      6          7       3
10     12         42       7
11     20         56       9
12     42         77      13
17     60        297      26
19    120        490      39
23    156       1255      79
29    168       4565     194
30    231       5604     230
31   1320       6842     265
44   3740      75175    1519
49   5040     173525    2754
57  23100     614154    6832
67  34807.5  2679689   20372
70  47058    4087968   27744

```

Curiously $K(N)$ is always an integer in this range, except for
$K(N) = 34807\!\frac12 = 2^{-1} \, 3^2 \, 5 \; 7 \; 13 \; 17$ for
$67 \leq N \leq 69$. Here's the **gp** code that generated this data
(in about 10 minutes):



```
S(v) = sum(i=1,#v,1/v[i])

{
K(n, v,p,c) =
  v = partitions(n);
  p = #v;
  v = vecsort(vector(p,i,S(v[i])));
  c = 1;
  while(v[c]<1,c++);
  [n, 1. / (1-v[c-1]), p, c]
}

\p 9
allocatemem(2^31)
#
for(n=2,72,print(K(n)))

```

*ADDED LATER:* Here's some further computational data. Using **gp-2.6**'s
new function **forpart** in place of **partitions**, and removing the
unnecessary sort, avoids using $p(n)$ space; we also save time by
not trying any partition with $n\_1=1$. This lets us extend the
calculation to $N=100$ in about half an hour. Here are the records
(now including two more non-integral values for $74 \leq N \leq 79$),
together with all partitions that attain them:



```
 N        K     n_i
 2        2     2
 5        6     2, 3
10       12     3, 3, 4
11       20     2, 4, 5
12       42     2, 3, 7
17       60     3, 4, 5, 5
19      120     3, 3, 5, 8
21      """     2, 5, 6, 8
23      156     3, 3, 4, 13
25      """     2, 4, 6, 13
29      168     3, 4, 7, 7, 8
30      231     2, 3, 11, 14
32      420     2, 4, 5, 21
33      """     3, 4, 5, 7, 14
38     1320     2, 5, 8, 11, 12
40     """"     4, 5, 6, 6, 8, 11
44     3740     2, 4, 10, 11, 17
47     """"     4, 5, 5, 5, 11, 17
49     5040     3, 4, 7, 9, 10, 16
56     """"     2, 7, 9, 10, 12, 16
57    23100     3, 4, 7, 7, 11, 25
64    """""     2, 7, 7, 11, 12, 25
66    """""     4, 6, 6, 7, 7, 11, 25
67    34807.5   3, 5, 7, 9, 13, 13, 17
70    47058     2, 3, 11, 23, 31
74    59690.4   2, 4, 11, 17, 19, 21
75    """""""   3, 4, 7, 11, 14, 17, 19
79    91162.5   3, 5, 5, 11, 13, 17, 25
80   200970     3, 5, 7, 7, 11, 18, 29
83   """"""     5, 6, 7, 7, 9, 9, 11, 29
89   """"""     5, 6, 6, 7, 7, 11, 18, 29
92   239085     5, 5, 7, 7, 7, 11, 23, 27
96   405720     2, 5, 8, 9, 23, 49

```

and here's the **gp-2.6** code:



```
\\ gp-2.6
S(v) = sum(i=1,#v,1/v[i])

{
K(n, p,p1,c,c1) =
  c = 0;
  p = [];
  forpart(p1=n, c1=S(p1); if((c1<1) && (c1>=c),
    if(c==c1, p=concat(p,[Vec(p1)]), c=c1; p=[Vec(p1)])
  ), [2,n]);
[n, 1./(1-c), p]
}

\p 10
#
for(n=2,100,print(K(n)))

```

