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?
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 v_p(n)$, which we might view as a random variable.
Let $E_n = frac1n sum_k=1^nOmega(k)$ be the expected value and $V_n=frac1n sum_k=1^n(E_n-Omega(k))^2$ be the variance.
Then
$$pi(n) approx fracngamma(fracV_nE_n,1.4854177cdot fracV_nE_n^2)Gamma(fracV_nE_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
$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 v_p(n)$, which we might view as a random variable.
Let $E_n = frac1n sum_k=1^nOmega(k)$ be the expected value and $V_n=frac1n sum_k=1^n(E_n-Omega(k))^2$ be the variance.
Then
$$pi(n) approx fracngamma(fracV_nE_n,1.4854177cdot fracV_nE_n^2)Gamma(fracV_nE_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
$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 v_p(n)$, which we might view as a random variable.
Let $E_n = frac1n sum_k=1^nOmega(k)$ be the expected value and $V_n=frac1n sum_k=1^n(E_n-Omega(k))^2$ be the variance.
Then
$$pi(n) approx fracngamma(fracV_nE_n,1.4854177cdot fracV_nE_n^2)Gamma(fracV_nE_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
$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 v_p(n)$, which we might view as a random variable.
Let $E_n = frac1n sum_k=1^nOmega(k)$ be the expected value and $V_n=frac1n sum_k=1^n(E_n-Omega(k))^2$ be the variance.
Then
$$pi(n) approx fracngamma(fracV_nE_n,1.4854177cdot fracV_nE_n^2)Gamma(fracV_nE_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
60.8k5153232
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
$$nfracgammaleft(1+o(1),frac1.4854177+o(1)loglog nright)Gammabigl(1+o(1)bigr)=nfrac1.4854177+o(1)loglog n.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
$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
$$nfracgammaleft(1+o(1),frac1.4854177+o(1)loglog nright)Gammabigl(1+o(1)bigr)=nfrac1.4854177+o(1)loglog n.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
$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
$$nfracgammaleft(1+o(1),frac1.4854177+o(1)loglog nright)Gammabigl(1+o(1)bigr)=nfrac1.4854177+o(1)loglog n.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
$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
$$nfracgammaleft(1+o(1),frac1.4854177+o(1)loglog nright)Gammabigl(1+o(1)bigr)=nfrac1.4854177+o(1)loglog n.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
$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
$$nfracgammaleft(1+o(1),frac1.4854177+o(1)loglog nright)Gammabigl(1+o(1)bigr)=nfrac1.4854177+o(1)loglog n.$$
On the other hand, $pi(n)$ is asymptotically $n/log n$ by the prime number theorem.
edited 7 hours ago
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