proof that 4x exceeds the product of the primes up to x

Statement. (Erdős & Surányi) Given the prime counting function π(x) and notating the ith prime as pi, the inequality


is always true for any nonnegative x. In other words, the xth power of 4 is greater than the primorial π(x)#.

Note: x is the integer nearest to the real number x that’s not greater than x, while x is the nearest integer to x that’s not smaller than x.

Proof. It takes very little computational effort to verify this is true for x set to 1 or 2. For larger x we can high-ball the primorial π(x)# as


(that is, twice the product of the odd numbersMathworldPlanetmathPlanetmath from 1 to x) and rephrase 4x as


The first factor is obviously the same for both expressions, both iterators have the same start value, but cleary the iterator end values satisfy the inequality (2x-1)>x2 as long as x>2. The first expression being iteratively multiplied clearly increases, but the second expression being iteratively multiplied is static (being a 2). This line of thought has failed to yield the desired result.

What if instead we divide both expressions by 2 and take their base 2 logarithms? Obviously, for half 4x,


giving us the sequence of odd numbers 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, etc. Not quite so obviously, for half our primorial high-ball, the base 2 logarithm is


(where log(x) is the natural logarithmMathworldPlanetmath and n!! is the double factorialMathworldPlanetmath), giving us the sequence (to 5 decimal places) 0, 1.58496, 1.58496, 3.90689, 3.90689, 6.71425, 6.71425, 9.88417, 9.88417, 13.3436, 13.3436, 17.044, 17.044, 20.9509, 20.9509, 25.0384, 25.0384, 29.2863, 29.2863, etc.

Unfortunately, both of these strategies are doomed to failure because eventually our high-ball for the primorial overtakes 4x. What Erdős and Surányi do instead is rephrase x as x=2n+1 and then construct the binomial coefficientDlmfDlmfMathworldPlanetmath (2n+1n) and showing the relationship of this to 2x.


  • 1 Paul Erdős & János Surányi Topics in the theory of numbers New York: Springer (2003): 5.11
Title proof that 4x exceeds the product of the primes up to x
Canonical name ProofThat4xExceedsTheProductOfThePrimesUpToX
Date of creation 2013-03-22 17:04:48
Last modified on 2013-03-22 17:04:48
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 7
Author PrimeFan (13766)
Entry type Proof
Classification msc 11A41
Classification msc 11A25
Classification msc 11N05