Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Riemann's Prime Power Counting Function

DZone 's Guide to

Riemann's Prime Power Counting Function

We look at this mathematical equation and how to model it using the Python and Mathematica languages. Read on to learn more!

· Big Data Zone ·
Free Resource

The prime number theorem says that π(x), the number of primes less than or equal to x, is asymptotically x/log x. So it's easy to estimate the number of primes below some number N. But what if we want to estimate the number of prime powers less than N? This is a question that comes up in finite fields, for example, since there is a finite field with elements if and only if n is a prime power. It's also important in finite simple groups because these groups are often indexed by prime powers.

Riemann's prime-power counting function Π(x) counts the number of prime powers less than or equal to x. Clearly Π(x) > π( x) for x ≥ 4 since every prime is a prime power, and 4 is a prime power but not a prime. Is Π(x) much bigger than π(x)? What is its limiting distribution, i.e. what is the analog of the prime number theorem for prime powers?

Numerical Examples

It turns out Π(x) equals π(x) asymptotically. That is, even though Π(x) is always bigger than π(x), their ratio converges to 1 as x increases.

Why is that? Let's first look at N = 1,000,000. The number of primes less than one million happens to be 78,498. The number of prime powers less than N is 78,734. So the latter includes only 236 prime powers with exponent greater than 1.

If we increase N to 1,000,000,000, there are 50,847,534 primes less than N and 50,851,223 prime powers, a difference of 3,689. Said another way, 99.99% of the prime powers less than a billion have exponent 1.

Equation for Π(x)

The number of prime powers less than N with exponent 2 equals the number of primes less than the square root of N. And the number of prime powers less than N with exponent 3 equals the number of primes less than the cube root of N. The number of prime powers with exponent 4 equals the number of primes less than the fourth root of N. Etcetera.

Even if N is large, these counts start getting small pretty soon. How soon? We're taking roots of order r until the rth root of N is less than 2, because then there are no more primes less than that root. That means we keep going until r > log 2N. And so we have the following equation:

Mathematica and Python Code

I looked in Mathematica and SymPy for a function to compute Π(x) and didn't see one. Maybe I missed something. But in either case it's easy to implement our own using the equation above.

In Mathematica:

pp[n_] := Sum[PrimePi[n^(1/r)], {r, 1, Log2[n]}]

In Python:

from sympy import primepi
from math import log2

def pp(n):
    top = int(log2(n))
    return sum(
        [primepi(n**(1/r)) for r in range(1, 1+top)]
    )
Topics:
number theory ,big data ,python ,mathematica

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}