A curious prime counting approximation or just data overfitting?Is Li(x) the best possible approximation to...
A curious prime counting approximation or just data overfitting?
Is Li(x) the best possible approximation to the prime-counting function?Estimate on the prime-counting function $psi(x)$.Asymptotic bounds on $pi^{-1}(x)$ (inverse prime counting function)Prime-Counting Functiona question for the prime counting functionThe shortest interval for which the prime number theorem holdsParity of the Prime Counting Functionprime counting function pi boundsnth prime better approximationPrime counting. Meissel, Lehmer: is there a general formula?
$begingroup$
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}^nOmega(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{ngamma(frac{V_n}{E_n},1.4854177cdot 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
omegas.append(Omega(n))
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)
xxs.append(xx)
means.append(m.N())
variances.append(v.N())
nt.number-theory analytic-number-theory prime-numbers prime-number-theorem
edited 7 hours ago
GH from MO
60.8k5153232
asked 8 hours ago
orgeslekaorgesleka
724417
$endgroup$
add a comment |
$begingroup$
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}^nOmega(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{ngamma(frac{V_n}{E_n},1.4854177cdot 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
omegas.append(Omega(n))
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)
xxs.append(xx)
means.append(m.N())
variances.append(v.N())
nt.number-theory analytic-number-theory prime-numbers prime-number-theorem
edited 7 hours ago
GH from MO
60.8k5153232
asked 8 hours ago
orgeslekaorgesleka
724417
$endgroup$
$begingroup$
Does $1.485...$ correspond to some known constant?
$endgroup$
– Sylvain JULIEN
7 hours ago
$begingroup$
I am not sure. Maybe.
$endgroup$
– orgesleka
7 hours ago
add a comment |
$begingroup$
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}^nOmega(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{ngamma(frac{V_n}{E_n},1.4854177cdot 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
omegas.append(Omega(n))
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)
xxs.append(xx)
means.append(m.N())
variances.append(v.N())
nt.number-theory analytic-number-theory prime-numbers prime-number-theorem
edited 7 hours ago
GH from MO
60.8k5153232
asked 8 hours ago
orgeslekaorgesleka
724417
$endgroup$
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}^nOmega(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{ngamma(frac{V_n}{E_n},1.4854177cdot 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
omegas.append(Omega(n))
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)
xxs.append(xx)
means.append(m.N())
variances.append(v.N())
nt.number-theory analytic-number-theory prime-numbers prime-number-theorem
nt.number-theory analytic-number-theory prime-numbers prime-number-theorem
edited 7 hours ago
GH from MO
60.8k5153232
asked 8 hours ago
orgeslekaorgesleka
724417
edited 7 hours ago
GH from MO
60.8k5153232
asked 8 hours ago
orgeslekaorgesleka
724417
edited 7 hours ago
GH from MO
60.8k5153232
edited 7 hours ago
GH from MO
60.8k5153232
edited 7 hours ago
GH from MO
60.8k5153232
60.8k5153232
asked 8 hours ago
orgeslekaorgesleka
724417
asked 8 hours ago
orgeslekaorgesleka
724417
asked 8 hours ago
orgeslekaorgesleka
724417
724417
$begingroup$
Does $1.485...$ correspond to some known constant?
$endgroup$
– Sylvain JULIEN
7 hours ago
$begingroup$
I am not sure. Maybe.
$endgroup$
– orgesleka
7 hours ago
add a comment |
$begingroup$
Does $1.485...$ correspond to some known constant?
$endgroup$
– Sylvain JULIEN
7 hours ago
$begingroup$
I am not sure. Maybe.
$endgroup$
– orgesleka
7 hours ago
$begingroup$
Does $1.485...$ correspond to some known constant?
$endgroup$
– Sylvain JULIEN
7 hours ago
$begingroup$
Does $1.485...$ correspond to some known constant?
$endgroup$
– Sylvain JULIEN
7 hours ago
$begingroup$
I am not sure. Maybe.
$endgroup$
– orgesleka
7 hours ago
$begingroup$
I am not sure. Maybe.
$endgroup$
– orgesleka
7 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your heuristic approximation is not correct. It was proved by Turán (1934) that
$E_n$ and $V_n$ are both asymptotically $loglog n$. As a result, the RHS of your display is
$$nfrac{gammaleft(1+o(1),frac{1.4854177+o(1)}{loglog n}right)}{Gammabigl(1+o(1)bigr)}=nfrac{1.4854177+o(1)}{loglog n}.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
$endgroup$
1
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "504"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f333258%2fa-curious-prime-counting-approximation-or-just-data-overfitting%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your heuristic approximation is not correct. It was proved by Turán (1934) that
$E_n$ and $V_n$ are both asymptotically $loglog n$. As a result, the RHS of your display is
$$nfrac{gammaleft(1+o(1),frac{1.4854177+o(1)}{loglog n}right)}{Gammabigl(1+o(1)bigr)}=nfrac{1.4854177+o(1)}{loglog n}.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
$endgroup$
1
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
add a comment |
$begingroup$
Your heuristic approximation is not correct. It was proved by Turán (1934) that
$E_n$ and $V_n$ are both asymptotically $loglog n$. As a result, the RHS of your display is
$$nfrac{gammaleft(1+o(1),frac{1.4854177+o(1)}{loglog n}right)}{Gammabigl(1+o(1)bigr)}=nfrac{1.4854177+o(1)}{loglog n}.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
$endgroup$
1
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
add a comment |
$begingroup$
Your heuristic approximation is not correct. It was proved by Turán (1934) that
$E_n$ and $V_n$ are both asymptotically $loglog n$. As a result, the RHS of your display is
$$nfrac{gammaleft(1+o(1),frac{1.4854177+o(1)}{loglog n}right)}{Gammabigl(1+o(1)bigr)}=nfrac{1.4854177+o(1)}{loglog n}.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
$endgroup$
Your heuristic approximation is not correct. It was proved by Turán (1934) that
$E_n$ and $V_n$ are both asymptotically $loglog n$. As a result, the RHS of your display is
$$nfrac{gammaleft(1+o(1),frac{1.4854177+o(1)}{loglog n}right)}{Gammabigl(1+o(1)bigr)}=nfrac{1.4854177+o(1)}{loglog n}.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
edited 7 hours ago
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
answered 7 hours ago
GH from MOGH from MO
60.8k5153232
60.8k5153232
1
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
add a comment |
1
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
1
1
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
$begingroup$
thanks. i thought that there must be some mistake
$endgroup$
– orgesleka
7 hours ago
add a comment |
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f333258%2fa-curious-prime-counting-approximation-or-just-data-overfitting%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Does $1.485...$ correspond to some known constant?
$endgroup$
– Sylvain JULIEN
7 hours ago
$begingroup$
I am not sure. Maybe.
$endgroup$
– orgesleka
7 hours ago