Integer odds and prime numbers

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. 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.

Leave a Reply

Your email address will not be published.