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?













3












$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







share|cite|improve this question











$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
















3












$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







share|cite|improve this question











$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














3












3








3





$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







share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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


















  • $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










1 Answer
1






active

oldest

votes


















8












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






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    thanks. i thought that there must be some mistake
    $endgroup$
    – orgesleka
    7 hours ago












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
});


}
});














draft saved

draft discarded


















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









8












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






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    thanks. i thought that there must be some mistake
    $endgroup$
    – orgesleka
    7 hours ago
















8












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






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    thanks. i thought that there must be some mistake
    $endgroup$
    – orgesleka
    7 hours ago














8












8








8





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






share|cite|improve this answer











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







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








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














  • 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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Taj Mahal Inhaltsverzeichnis Aufbau | Geschichte | 350-Jahr-Feier | Heutige Bedeutung | Siehe auch |...

Image
Mogul-ArchitekturMausoleum in IndienBauwerk in Uttar PradeshGrabmoscheeKuppelbauwerkWeltkulturerbe in AsienWeltkulturerbe in IndienAgraMogulreichGrabbau in AsienGrabgartenErbaut in den 1640er Jahren deutschpersoarabischDMGDevanagariMausoleumYamunaAgraindischenUttar PradeshKuppelMinaretteZiegelsteinenMarmorplattenGroßmogulShah JahanMumtaz MahalOktogonTambourgebauchtenChhatriIwanMinaretteErdbebenWendeltreppeJaliKenotapheKryptaReliefsMarmorinkrustationenKoranMärtyrerinGottesSandsteinTschahār BāghBagh-e WafaDschalalabadParadiesgartenMekkaMoscheeSüd-ZentralasiensAhmad LahoriBadakhshanAbu Fazelpersische Architekturindo-islamischen BaukunstIndienAsiensElefantenMarmorJaipurRajasthanNarbadaEdelsteinenHalbedelsteinenJaspisPunjabKarneoleAchatYemenKristallChinaLapislazuliSaphireCeylonKorallenArabienRoten MeerGranateBundelkhandDiamantenPannaOnyxPersienHeliotropFatehpur SikriTürkiseJean-Baptiste TavernierFrançois BernierMullahsSeelenTeppichenYamunaMuhammad Aurangzeb AlamgirTschahār BāghHumayunsbri...
Read more

Baia Sprie Cuprins Etimologie | Istorie | Demografie | Politică și administrație | Arii naturale...

Image
Localități urbane în județul MaramureșOrașe în județul MaramureșBaia Sprie maghiarăgermanăorașjudețul MaramureșTransilvaniaRomâniaChiuzbaiaTăuții de SusSatu Nou de Susminieresașilor13291329maghiarCarol RobertBaia Mare13601348139014061851latinescul1540germanBaia Mare1564Nicolae OlahusSăsarGutâiBaia Mare1411Belgradului1427Iancu de Hunedoara14461453Matei CorvinMaria Terezaslovacirecensământului efectuat în 2011recensământul anterior din 2002românimaghiariromiortodocșiromano-catolicireformațigreco-catolicipenticostalimartori ai lui IehovaSebastian Alin BârdaPartidul Național Liberal178019321960școlii băimărene de picturăAurel PoppAdy EndreNicolae TonitzaAstra19221997România1876vulcanicetectonicădaciteandezitecuarțuluiBaia SprieBorșaCavnicDragomireștiSăliștea de SusSeiniȘomcuta MareTârgu LăpușTăuții-MăgherăușUlmeniVișeu de SusArdusatArinișAsuaju de SusBăița de sub CodruBăiuțBârsanaBăseștiBicazBistraBocicoiu MareBogdan VodăBoiu MareBotizaBudeștiCălineștiCâmpulung la TisaCerneștiCicârlăuCoa...
Read more

Nicolae Petrescu-Găină Cuprins Biografie | Opera | In memoriam | Varia | Controverse, incertitudini...

Image
Articole de calitateNașteri în 1871Nașteri pe 31 martieDecese în 1931Decese pe 15 februarieArtiști români din secolul al XIX-leaArtiști români din secolul al XX-leaCaricaturiști româniTinerimea artistică CraiovaRomâniaBucureștiRomâniacaricaturistȘtefan LuchianConstantin ArtachinoAlexandru Bogdan-PiteștiNicolae Vermont1898Honoré DaumierParlamentului României19081913Constantin Jiquidi1898secolului al XIX-leaGolemo KonjariBulgariaMuzeului de Artă din Craiova2007Craiova31 martie1871limba francezălimba latinăLiceul Sfântul SavaBucureștigazului metanOperei RomâneȘtefan Petrescu-MuscăLiceul „Carol I”Școlii de Belle-ArteCostin PetrescuGheorghe TattarescuTheodor AmanConstantin I. StăncescuAlexandru ObedenaruSalonului Artiștilor IndependențiExpoziția Artiștilor în ViațăNicolae VermontȘtefan LuchianConstantin ArtachinoAlexandru Bogdan-PiteștiIon AngelescuNicolae GrantIon TicuLudovic DolinskiCaricatura Eu Sunt... Școala de Belle-Arte din BucureștiAteneului RomânGeorge RanettiCafeneaua ImperialFi...
Read more