$\operatorname{ GPF}(n)=$Greatest prime factor of $n$, eg. $\operatorname{ GPF}(17)=17$, $\operatorname{ GPF}(18)=3$.

$\operatorname{ LPF}(n)=$Least prime factor of $n$, eg. $\operatorname{ LPF}(17)=17$, $\operatorname{ LPF}(18)=2$.

$P_n=n$'th prime number, eg. $P_5=11$.

How to evaluate convergence/divergence/value of the sums

$$\sum_{n=2}^{\infty} \frac{1}{n\operatorname{ LPF}(n)}\,?$$

$$\sum_{n=2}^{\infty} \frac{1}{P_n\operatorname{ LPF}(n)}\,?$$

$$\sum_{n=2}^{\infty} \frac{1}{\operatorname{ GPF}(n)\operatorname{ GPF}(n+1)}\,?$$

$$\sum_{n=2}^{\infty} \frac{1}{\operatorname{ GPF}(n)\operatorname{ GPF}(n+1)\operatorname{ GPF}(n+2)}\,?$$

How to prove this diverges? $$\sum_{n=2}^{\infty} \frac{1}{\operatorname{ GPF}(n)\operatorname{ GPF}(n+1)\operatorname{ GPF}(n+2)...\operatorname{ GPF}(n+1000)}\,?$$


Evaluating $\sum\limits_{n=1}^{\infty} \frac{1}{n\operatorname{ GPF}(n)}$, where $\operatorname{ GPF}(n)$ is the greatest prime factor

  • 6
    $\begingroup$ Just wondering -- you've posted a series of similar questions. People, including me, have had fun playing with them. But is there some application for these? $\endgroup$ – Ben Crowell Feb 7 '12 at 18:06
  • $\begingroup$ You probably want to start at $n=2$, not $n=1$, since $1$ does not have either a GPF or LPF. $\endgroup$ – Robert Israel Feb 7 '12 at 18:09
  • 1
    $\begingroup$ @LLLLL: I also had fun working on a related question you asked, but would appreciate knowing whether these are book or homework questions, preparation for a paper submission, or something else. $\endgroup$ – bgins Feb 9 '12 at 16:26
  • $\begingroup$ These are questions. Thats all you need to know. $\endgroup$ – TROLLHUNTER Feb 9 '12 at 17:46
  • 6
    $\begingroup$ @LLLLL: It's awkward that you haven't shared with us any of your own thoughts on these problems. Your post saying "These are questions. That's all you need to know" could be considered offensive; this is not a polite attitude to demonstrate toward people who are trying to help you. People who are evidently very knowledgeable about number theory are saying that these are difficult research-level problems. If you want people to start collaborating with you on a problem whose solution would probably be publishable, it would make sense to be more forthcoming about what's going on. $\endgroup$ – Ben Crowell Feb 9 '12 at 21:33

I can prove the third series diverges, but I don't believe it is known whether or not the fourth, or the more general series, converge. (It is a hard problem, see the remarks at the end)

There is a very good survey paper on integers without large prime factors by Hildebrand and Tenenbaum. They go over the history of results about $\psi(x,y),$ and the Dickmann Debruijn function. For your particular question, we are interested in

$$\psi_F(x,y):=\left|\left\{ 1\leq n\leq x:\ P\left(F(n)\right)\leq y\right\} \right|$$ where $F$ is any integer valued polynomial. There are few results regarding general polynomials, and some regarding particular cases, fortunately one of which fits exactly this problem. In Hildebrand's paper On integer sets containing strings of consecutive integers, he proves that for $F(x)=\prod_{1\leq j\leq k}(x+j)$, we have $$\psi_F(x,x^\alpha)\asymp_{\alpha,k} x$$ provided $\alpha>e^{-1/(k-1)}.$ Now, I could not access the paper on the Cambridge journal site, so I have not actually read it, but this result is referred to in the related paper Polynomials values free of large prime factors by Dartyge, Martin and Tenenbaum which is where I first saw it.

Divergence of third series: For $k=2$, the number of $n\leq x$ such that $n(n+1)$ has no prime factors greater then $x^{1/e+\delta}$ is bounded below by a positive constant multiple of $x$. From this it follows that the set $$S:=\{n:\ P(n),\ P(n+1)\leq n^{\frac{1}{e}+\delta}\}$$ is dense in the integers.** Since $$\frac{1}{P(n)P(n+1)}\geq \frac{1}{P(n(n+1))^2},$$ by restricting the sum to the set $S$, we are summing $\frac{1}{n^{0.74}}$ over dense subset of integers, and hence the series diverges. (A monotonic positive sequence whose series diverges, still diverges when restricted to any dense subset)

The problem for the fourth series and higher: We could try the same thing for the fourth series, and look at $k=3$ above. However, we can only take $\alpha=\frac{1}{\sqrt{e}}\approx 0.6$, and we have three terms which takes us to $n^{1.8}$, and that series converges. If we could lower the bound on $\alpha$ in Hildebrand's Theorem to $\alpha>\frac{1}{k+\delta}$ instead of $\alpha>e^{-1/(k-1)}$, then the series would diverge for any number of consecutive terms. I think this is likely true, and proving it would be interesting, but it is not that easy.

** We have to be careful when switching from $P(n)\leq x^{1/e+\delta}$ on an interval, to showing the set $S$ is dense, since $S$ is defined with the condition $P(n)\leq n^{1/e+\delta}$. To make the switch rigorously, lets take $\delta/2$, and then look at the interval $(x^{1-\delta/2},x)$. We know there will be at least $cx$ integers $n$ such that $n(n+1)$ has no prime factor greater then $x^{1/e+\delta/2}$. For these $n$, the same condition holds with $P(n(n+1))\leq n^{1/e+\delta}$, so there are at least $cx$ integers $n\in S$. This holds for every interval, so $S$ is dense.


The first diverges, just look at the terms with even $n$. The sum of these "is" $\sum_{k=1}^\infty \frac{1}{4k}$.

The second diverges, by Euler's result on divergence of $\sum\frac{1}{p_n}$. Note that Euler's result implies that $\sum \frac{1}{p_{2n}}$ diverges, and putting an additional $2$ in the denominator doesn't help.

The third problem is potentially difficult. Convergence, if it happens, will be very slow.


I suspect that the asymptotic density of integers $n$ with $GPF(n) \le \sqrt{n}$ is positive (and I wouldn't be surprised if this is provable). That being the case, it's also likely (but maybe not provable with current techniques) that the asymptotic density of integers $n$ with $GPF(n) GPF(n+1) \le n$ is also positive, and therefore that series 3 diverges.

EDIT: in fact, the asymptotic density of integers with $GPF(n) \le \sqrt{n}$ is $\rho(2) = 1 - \ln 2$ where $\rho$ is the Dickman-de Bruijn function.

  • $\begingroup$ In fact, the asymptotic density of integers $n$ with $GPF(n) \leq n^\alpha$ is positive for any $\alpha$, so this seems very likely (but still likely out of reach) - good catch! $\endgroup$ – Steven Stadnicki Feb 7 '12 at 18:42
  • $\begingroup$ Actually, with the problem phrased this way, the divergence of that third sum feels like it might be within reach - having 30% of numbers meet the hypothesis is a LOT, and while physical arguments would only work for a proportion $\gt 50\%$, even a proportion around that 30% forces such sharp constraints on the structure of 'failing' numbers that it seems like it might be possible to prove that a positive proportion of numbers have $GPF(n)\leq\sqrt{n}$ and $GPF(n+1)\leq\sqrt{n}$ with some relatively elementary argument... $\endgroup$ – Steven Stadnicki Feb 8 '12 at 7:26
  • 1
    $\begingroup$ It's a moot point given Eric's answer, but what this does show is that at least one of $\sum_n 1/(GPF(n) GPF(n+1))$, $\sum_n 1/(GPF(n) GPF(n+2))$, $\sum_n 1/(GPF(n) GPF(n+3))$ diverges. $\endgroup$ – Robert Israel Feb 10 '12 at 20:03

While I don't have an answer for the third problem, I think it's worth pointing out the difference between this and the previous problem that makes this problem almost certainly intractable while so much progress was made on the other. The question about $\Sigma 1/n\mathrm{GPF}(n)$ has, despite the sum up front, an essentially multiplicative nature - the fact that $n$ is bundled with its own greatest prime factor allows the sum to be turned 'inside out' and expressed in terms of a sum over primes, letting convergence be proved by comparing sequences.

By contrast, this problem bundles $n$ with $n+1$, layering an additive structure on the problem - and virtually nothing is known about the additive structure of primes and factoring. I think it's safe to say that there's a general consensus that factoring 'behaves randomly' with respect to addition; that is, that aside from not being factorable by the numbers that are factors of $n$, the factorization of $n+1$ 'looks like' the factorization of any other number of roughly that size - but no one knows how to prove anything like this; every conjecture of this nature that you can think of (the Twin Primes conjecture, the infinitude of Mersenne primes or even of primes next to smooth numbers) is (as far as I know, anyway) open. It feels safe to say that your third problem is likely well out of reach of current mathematics. (EDIT: let this be a lesson to always be careful what you say is 'well out of reach'! In fact, as noted between Robert Israel's excellent answer below and Eric Naslund's comments, the divergence of this series is already provable; the key point is presumably that the density of numbers with 'small enough' greatest prime factors is so high (i.e., positive) that it's possible to prove they must occur consecutively often enough.)

  • 2
    $\begingroup$ Eric: thanks - looking back I'm not a big fan of it either. It felt plausible initially but after Robert's excellent answer it started to feel like the result might be within reach after all; I'm . I'm inclined to leave my comment in place but may add a quick edit to note that this one was within striking distance after all. :-) I'm really looking forward to seeing your writeup! $\endgroup$ – Steven Stadnicki Feb 9 '12 at 1:11
  • $\begingroup$ I knew I had to look at things carefully. The result of hildebrand has a stronger condition on $\alpha$ then what I was thinking last night. In the end we can prove the divergence of the third series, but the fourth is still inconclusive! To prove that it diverges, I think we would need to improve the result of Hildebrand. $\endgroup$ – Eric Naslund Feb 9 '12 at 18:55
  • $\begingroup$ I think my first comment was unfair, your thoughts about the problem being out of reach of modern mathematics were quite well founded and accurate. For the three terms, we needed a result from about 20 years ago which is complicated. And what might be a bit hypocritical, I am convinced that for four terms and higher the solution is unknown. $\endgroup$ – Eric Naslund Feb 9 '12 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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