I am not sure, if this is a research problem. If not I will move this question to ME: Let $\Omega(n) = \sum_{p|n} v_p(n)$, which we might view as a random variable. Let $E_n = \frac{1}{n} \sum_{k=1}^n\Omega(k)$ be the expected value and $V_n=\frac{1}{n} \sum_{k=1}^n(E_n-\Omega(k))^2$ be the variance. Then $$\pi(n) \approx \frac{n\gamma(\frac{V_n}{E_n},1.4854177\cdot \frac{V_n}{E_n^2})}{\Gamma(\frac{V_n}{E_n})}$$ where $\Gamma=$ Gamma function, $\gamma=$ lower incomplete gamma function.

Background: I was trying to fit the gamma distribution to the random variable $\Omega(k)$ ,$1 \le k \le n$. The value $1.4854177$ is fitted to some data. My question is, if there is any heuristic why this approximation should be good, if at all, or if this is just an overfitting problem?

Below you can find some sage code which implements this:

def Omega(n):
    return sum([valuation(n,p) for p in prime_divisors(n)])

means = []
variances = []
xxs = []
omegas = [Omega(k) for k in range(1,10^4)]
for nn in range(10^4,10^4+3*10^3+1):
    n = nn
    print "---"
    m = mean(omegas[1:-1])
    v = variance(omegas[1:-1])
    shape,scale = m^2/v,v/m
    xx = find_root(lambda xx : n*(lower_gamma(shape,xx*1/scale)/gamma(shape) ).N()-prime_pi(n),1,2)
    xx = 1.4854177706344873
    approxPrimePi2 = n*(lower_gamma(shape,xx*1/scale)/gamma(shape) ).N()
    primepi = prime_pi(n)
    print primepi, approxPrimePi2,shape.N(),scale.N(),xx
    print "---"
    print "err2 = %s" % (abs(primepi-approxPrimePi2)/primepi)
  • 1
    $\begingroup$ Does $1.485...$ correspond to some known constant? $\endgroup$ – Sylvain JULIEN Jun 4 at 19:19
  • $\begingroup$ I am not sure. Maybe. $\endgroup$ – orgesleka Jun 4 at 19:20

Your heuristic approximation is not correct. It was proved by Turán (1934) that $E_n$ and $V_n$ are both asymptotically $\log\log n$. As a result, the RHS of your display is $$n\frac{\gamma\left(1+o(1),\frac{1.4854177+o(1)}{\log\log n}\right)}{\Gamma\bigl(1+o(1)\bigr)}=n\frac{1.4854177+o(1)}{\log\log n}.$$ On the other hand, $\pi(n)$ is asymptotically $n/\log n$ by the prime number theorem.

  • 2
    $\begingroup$ thanks. i thought that there must be some mistake $\endgroup$ – orgesleka Jun 4 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.