# Sharp upper bounds for sums of the form $\sum_{p \mid k} \frac{1}{p+1}$

Are there known sharp upper bounds (in terms of $k$ or $\omega(k)$, the number of distinct prime divisors of $k$) for sums of the form $\sum_{p \mid k} \frac{1}{p+1}$ for $k > 1$ subject to the constraint $\sum_{p \mid k} \frac{1}{p+1} < 1$? (This would be a special case of the general result of O. Izhboldin and L. Kurliandchik referenced in the comment.)

A related question: Suppose $(p_i)$ is a set of $n$ consecutive primes which minimizes $1 - \sum_{i = 1}^n \frac{1}{p_i+1} > 0$ for a given $n > 1$. Are there known bounds for $1 - \sum_{i = 1}^{n} \frac{1}{p_i + 1}$ from below in terms of $n$, e.g., $n^{-\delta n}$ for some fixed $\delta > 0$?

Thanks!

-
It is known (and hard) that if $\sum 1/n_i<1$ for positive integers $n_i$ ($i=1,2,\dots,k$), then $\sum_{i=1}^k 1/n_i\leq \sum_{i=1}^k 1/d_i$, where $d_1=2$, $d_{n+1}=d_1d_2\dots d_n+1$. –  Fedor Petrov Oct 23 '10 at 19:50
A reference for the result Fedor mentions is O. Izhboldin and L. Kurliandchik, Unit fractions, Proc. St. Petersburg Math. Soc. 3 (1995) 193--200. This appears in English translation in Amer. Math. Soc. Translations, Series 2, 166. –  Gerry Myerson Oct 23 '10 at 23:43
This was also asked on math.SE math.stackexchange.com/questions/7569/… –  George Lowther Oct 25 '10 at 0:36

It seems from your notation and the second part of your question that you are summing over the prime divisors. In that case there is no need to mention $k$ and one can get arbitrarily close to 1. There is an infinite sequence $2,3,5,7,11,29,127,1931,309121,47777896349 \dots$ where each term is the smallest prime not already listed which keeps $\sum \frac{1}{p+1}$ strictly less than 1. The sum for $2,3,5,7,11,23$ is exactly 1. Curiously, the partial sums starting with $\frac{3}{4}$ have the form $\frac{t-1}{t}$ until about the 11th term.

Pick a prime $p=p_1$ and consider $\sum_{i=1}^{n}\frac{1}{p_i+1}$ where the $p_i$ are consecutive primes and $n=n(p)$ is the largest integer which keeps the sum under 1.

$n(2)=5,n(3)=13,n(5)=37,n(7)=84,n(11)=171$ (The 171 primes from 11 to 1039 have $\sum \frac{1}{p+1}$ about $1-\frac{1}{5261}$. The 290 primes from 13 to 1933 have $\sum \frac{1}{p+1}$ about $1-\frac{1}{10179}$). Based on very limited evidence, it seems possible that $1-\sum_{i=1}^{n}\frac{1}{p_i+1}>\frac{1}{n^2}$ for $n>n(7)=84$. However I certainly can't rule out it being freakishly close to 1.

-
Perhaps OP is asking for upper bounds in terms of the number of summands. –  Gerry Myerson Oct 24 '10 at 22:32

If we are allowed to consider somewhat weaker bounds, both answers depend only on the number of unitary divisors of $k$, which is $2^{\omega(k)}$. By the quoted result of O. Izhboldin and L. Kurliandchik (see Fedor's and Myerson's comments), for any set of $n$ positive integers {$a_{1}, \dots, a_{n}$} such that $\sum_{i = 1}^{n} \frac{1}{a_{i}} <1$, we have \begin{eqnarray} \sum_{i = 1}^{n} \frac{1}{a_{i}} \leq \sum_{i = 1}^{n} \frac{1}{d_{i}} = \frac{d_{n+1} - 2}{d_{n+1} -1} < 1, \end{eqnarray} where $d_{i}$ is the $i^{\text{th}}$-Euler number, which satisfies the quadratic recurrence $d_{i} = d_{1} \cdots d_{i-1} + 1$ with $d_{1} = 2$. The first few terms of the sequence are 2, 3, 7, 43, 1807.... (A000058). It is relatively straightforward to show that the aforementioned recurrence is equivalent to $d_{i} = d_{i-1}(d_{i-1}-1) + 1$, and it is known from the recurrence that $d_{i} = \lfloor \theta^{2^{i}} + \frac{1}{2} \rfloor$, where $\theta \approx 1.2640$.... Thus, \begin{eqnarray} \sum_{p \mid k} \frac{1}{p + 1} \leq \sum_{i = 1}^{\omega(k)} \frac{1}{d_{i}} = \frac{d_{\omega(k) + 1} - 2}{d_{\omega(k)+1} - 1} = \frac{\lfloor \theta^{2^{\omega(k) + 1}} + \frac{1}{2} \rfloor - 2}{\lfloor \theta^{2^{\omega(k) + 1}} + \frac{1}{2} \rfloor - 1}. \end{eqnarray} One can also show that $d_{i} - 1 = \lfloor \vartheta^{2^{i-1}} - \tfrac{1}{2} \rfloor$, where where $\vartheta \approx 1.5979$...., so we have \begin{eqnarray} 1 - \sum_{p \mid k} \frac{1}{p + 1} \geq 1 - \frac{d_{\omega(k)+1} - 2}{d_{\omega(k)+1} - 1} = \frac{1}{d_{\omega(k)+1} - 1} = \lfloor \vartheta^{2^{\omega(k)}} - \tfrac{1}{2} \rfloor^{-1} > 0. \end{eqnarray}

Remark E. Deutsche points out that the sequence {$d_{i} - 1$} (A007018) counts the number of ordered rooted trees with out-going degree up to 2 with all leaves at top level.

-
Can it really be that $d_i=\lfloor\theta^{2^i}+(1/2)\rfloor$ where $\theta\approx1.264$, while $d_i-1=\lfloor\vartheta^{2^i}-(1/2)\rfloor$ where $\vartheta\approx1.5979$? –  Gerry Myerson Nov 1 '10 at 4:33
Also, the bounds given in this answer can't be the sharp bounds you asked for since (for example) it's impossible to have $p+1=d_1=2$. For $\omega(k)=2$ it would seem that the sharp bound is $(1/3)+(1/4)=7/12$ obtained for $k=6$. –  Gerry Myerson Nov 1 '10 at 4:39
Right, it's not as sharp as I'd like. For the case that you mention, 7/12 = 1/(2+1) + 1/(3+1) <= 1/2 + 1/6 = 2/3 isn't best possible but it'll do until I have a better understanding of the sequence 3,4,6,8,12,30,128,1932,309122... –  user02138 Nov 1 '10 at 5:19
As for the double exponential growth formulas that I quote above, see OEIS entries, along with Wikipedia and MathWorld articles for "Sylvester's Sequence". –  user02138 Nov 1 '10 at 5:51
Never mind those websites, I'm asking YOU: does it make sense that $d_i$ is pretty much $a^{2^i}$ while $d_i-1$ is pretty much $b^{2^i}$ for some $b$ not equal to $a$? I mean, take $i=3$, say, and calculate those powers, and make your own judgement as to what's reasonable. –  Gerry Myerson Nov 1 '10 at 12:00