Integer odds and prime numbers

Posted on by John

For every integer m > 1, it’s possible to choose N so that the proportion of primes in the sequence 1, 2, 3, … N is 1/m. To put it another way, you can make the odds against one of the first N natural numbers being prime any integer value you’d like [1].

For example, suppose you wanted to find N so that 1/7 of the first N positive integers are prime. Then the following Python code shows you could pick N = 3059.

    from sympy import primepi

    m = 7

    N = 2*m
    while N / primepi(N) != m:
        N += m
    print(N)

Related posts

[1] Solomon Golomb. On the Ratio of N to π(N). The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 36-37.

The proof is short, and doesn’t particularly depend on the distribution of primes. Golomb proves a more general theorem for any class of integers whose density goes to zero.

One thought on “Integer odds and prime numbers”

  1. Nathan Hannon

    A faster version, using a binary search:

    import math
from sympy import primepi

m = 20

low = 0
high = math.inf
mid = 2 ** math.ceil(m / math.log(2))
# initial guess of approximately exp(m), avoiding overflow error

primecount = primepi(mid * m)

while primecount != mid:
    if primecount < mid:
        high = mid
    else:
        low = mid
    if high == math.inf:
        mid = low * 2
    else:
        mid = (low + high) // 2
    primecount = primepi(mid * m)
        
print(mid * m)

    With m = 20 it takes about a minute to run on my not-exactly-new computer. It could be sped up more if we re-implemented the sieve algorithm used in primepi to take advantage of the fact that we are calculating it for multiple values and we know the approximate range of those values.

Comments are closed.