Site map 

 Contact Graeme 

 Skip Navigation LinksMath Help > Number Theory > Prime > Reciprocals of Primes

A "large" subset of positive integers is one whose sum-of-reciprocals diverges, whereas a "small" subset of positive integers has a convergent sum-of-reciprocals.  The odd positive integers, for example, is a "large" set.  The squares, on the other hand, is "small".

What about the primes?  Is this set large or small?  Answer: the primes are large -- the sum of reciprocals of primes diverges.

The sum of reciprocals of primes diverges

which is the number of positive integers n less than x which are divisible only by primes among the first i primes

Lemma 1: The number of positive integers less than x which are divisible only by primes among the first i primes is less than sqrt(x) 2i 

Let N(x) be the number of positive integers, n, whose only prime factors are p1, p2, ..., pi, the first i primes.

Any such n can be written k m2, where k is squarefree.  k is the product of a subset of the first i primes, each used at most once, so the number of choices of k is the number of subsets of the first i primes, which is 2i.  

m2 ≤ n < x, so the number of choices of m is at most sqrt(n), which is less than sqrt(x), so N(x) < sqrt(x) 2i  

Proof that The sum of reciprocals of primes diverges:

Suppose the sum converges.  Then there is an integer, i, such that the "tail" of the series beyond the ith term has a sum less than 1/2:

1/pi+1 + 1/pi+2 + 1/pi+3 ... < 1/2

The number of positive integers, n, less than x which are divisible by p is at most x/p, hence those divisible by any prime other than the first i primes, x - N(x), is at most

x/pi+1 + x/pi+2 + x/pi+3 ... < x/2

Since x-N(x) < x/2, it follows that x/2 < N(x), and from Lemma 1, N(x) < sqrt(x) 2i, so

x/2 < sqrt(x) 2i 

Now, let x = 22i+2, so

22i+1 < 2i+1 2i 

But this is false, so our original assumption, that the sum converges, could not be true, proving the result.

An Infinite Number of Primes Contain the String of Digits, "2004".


For every positive integer, n, divide the number into four digit "chunks", and treat the whole thing as a base-10000 number.  One of the symbols, d, in this base-10000 number system is "2004".

The sum of reciprocals of numbers that can be written without using digit d, base r, converges.  (Proof)

So the set of integers that do not contain "2004" aligned with a four-digit "chunk" is small.  The set of integers that do not contain "2004" at all is a subset of this set, so it is small, too.

If only a finite number of primes contain "2004", then there exists a prime, Pk, that is larger than the largest prime that contains "2004".

The set {Pk, Pk+1, ...} isn't small, however, because the primes are large.  So the set of primes at least as big as Pk can't be a subset of the set of integers that do not contain "2004".  So at least one element of this set of primes at least as big as Pk must contain "2004", a contradiction.

The slowest diverging series

 . . . . . . this section should be moved to a new page, related-to and in the same section as the page of convergence tests.  The slowest converging sequence would be the reciprocals of numbers not containing certain substrings (like the 2004 example above, except perhaps with ever-larger missing substrings)

Consider the following function:

logplex(x) = x, when x < e
logplex(x) = x ln(x), when e <= x < e^e
logplex(x) = x ln(x) ln(ln(x)), when e^e <= x < e^e^e
logplex(x) = x ln(x) ln(ln(x)) ln(ln(ln(x))), when e^e^e <= x < e^e^e^e

(As an aside, this function is easily implemented in VBA as

  Function logplex(ByVal a As Double) As Double
    logplex = a
    Do While a > Math.Exp(1)
      a = Math.Log(a)
      logplex = logplex * a
  End Function

but I digress...)

The question I investigated is this: given this definition of logplex, does the series 1/logplex(1) + 1/logplex(2) + 1/logplex(3) + ... converge?

To answer this question, I found the integral from e^^n to e^^(n+1) of dx/logplex(x), (where e^^n is a tower of height n of e^e^...^e using Knuth's "up arrow" notation), which, interestingly, does not depend on n.

The sequence, 1/logplex(n), converges to zero a bit faster than 1/n, and yet the sum of the elements of this sequence diverges. Is there an even faster-converging sequence with a divergent sum?

Internet references

From the Prime PagesThere are Infinitely Many Primes, but How Big of an Infinity?

Planet Math: Knuth's "up arrow" notation

Related pages in this website



The webmaster and author of this Math Help site is Graeme McRae.