MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?


share|cite|improve this question
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… – 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.

Your the lead in of your second question could be reworked into:

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.

share|cite|improve this answer
Perhaps OP is asking for upper bounds in terms of the number of summands. – Gerry Myerson Oct 24 '10 at 22:32
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.