Prime numbers and primality testing is a Restricted Group with 1111 members.
 Prime numbers and primality testing

 Restricted Group,
 1111 members
Primary Navigation
What if Riemann's primecounting formula was not the best?
Expand Messages
 0 Attachment
What if another, easier to use formula, would fit better with pi(x)?
Check it out at:
http://www.slideshare.net/ChrisDeCorte1/betterprimecountingformula 0 Attachment
 In primenumbers@yahoogroups.com,
"chrisdecorte" <chrisdecorte@...> wrote:
> What if Riemann's primecounting formula was not the best?
Perhaps it might be a good idea to find out what Riemann's
formula is? Then try comparing your Excel powerlaw fits
with Gram's convenient version of Riemann's formula, which
you will find in Eq (12) at
http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html
Here is R(10^k) for k = 1 to 10:
R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
for(k=1,10,print([k,round(R(10^k))]))
[1, 5]
[2, 26]
[3, 168]
[4, 1227]
[5, 9587]
[6, 78527]
[7, 664667]
[8, 5761552]
[9, 50847455]
[10, 455050683]
Over to Excel :)
David 0 Attachment
Please find attached the comparison.
To be more correct, I should also know the pi(x) so that I can finetune my formula as well.
________________________________
From: djbroadhurst <d.broadhurst@...>
To: primenumbers@yahoogroups.com
Sent: Sunday, July 28, 2013 12:46 PM
Subject: [PrimeNumbers] Re: What if Riemann's primecounting formula was not the best?
 In primenumbers@yahoogroups.com,
"chrisdecorte" <chrisdecorte@...> wrote:
> What if Riemann's primecounting formula was not the best?
Perhaps it might be a good idea to find out what Riemann's
formula is? Then try comparing your Excel powerlaw fits
with Gram's convenient version of Riemann's formula, which
you will find in Eq (12) at
http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html
Here is R(10^k) for k = 1 to 10:
R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
for(k=1,10,print([k,round(R(10^k))]))
[1, 5]
[2, 26]
[3, 168]
[4, 1227]
[5, 9587]
[6, 78527]
[7, 664667]
[8, 5761552]
[9, 50847455]
[10, 455050683]
Over to Excel :)
David

Unsubscribe by an email to: primenumbersunsubscribe@yahoogroups.com
The Prime Pages : http://primes.utm.edu/
Yahoo! Groups Links
[Nontext portions of this message have been removed] 0 Attachment
 In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:
> > What if Riemann's primecounting formula was not the best?
http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html
>
> Perhaps it might be a good idea to find out what Riemann's
> formula is? Then try comparing your Excel powerlaw fits
> with Gram's convenient version of Riemann's formula, which
> you will find in Eq (12) at
PS: Eric's Eq (11) is the last equation of Riemann's MS of 1859:
http://www.claymath.org/millennium/Riemann_Hypothesis/1859_manuscript/riemann1859.pdf
David 0 Attachment
Chris
In the Wikipedia article titled �Primecounting function�
http://en.wikipedia.org/wiki/Primecounting_function
the value of Pi(10^24) is exactly 18,435,599,767,349,200,867,866.
Your �preferred formula�
Pi(x) = alpha*x^beta with alpha=0.2083666 and beta=0.9294465 gives
only 4,222,251,563,919,881,535,488 which is out by a factor of 4+ !!
You may want to study some elementary books on Number Theory to
understand why Riemann�s function gives the best asymptotic value
as the number of primes tends towards infinity.
Regards
Alan
[Nontext portions of this message have been removed] 0 Attachment
chrisdecorte wrote:> What if another, easier to use formula, would fit better with pi(x)?
Your pi(x) approximation without relying on different formulas for
>
> Check it out at:
>
> http://www.slideshare.net/ChrisDeCorte1/betterprimecountingformula
different small x ranges is c(x) = 0.2083666*x^0.9294465.
The prime number theorem shows pi(x)/c(x) tends to infinite but
your paper says:
"We especially wanted to focus on the set of primes that were
probably unknown in the time of Riemann."
So let's make a comparison with exactly computed pi(x) values.
x/log(x) and x/(log(x)1) are the commonly used approximations
not using li(x) or long formulas.
// http://oeis.org/A006880 Number of primes < 10^n
{A006880=[4,25,168,1229,9592,78498,664579,5761455,50847534,
455052511,4118054813,37607912018,346065536839,3204941750802,
29844570422669,279238341033925,2623557157654233,24739954287740860,
234057667276344607,2220819602560918840,21127269486018731928,
201467286689315906290,1925320391606803968923,
18435599767349200867866,176846309399143769411680];}
c(x)=0.2083666*x^0.9294465;
\p 5
print("x, pi(x)/c(x), pi(x)/(x/log(x)), pi(x)/(x/(log(x)1))");
for(n=1,#A006880,x=10^n;p=A006880[n];\
print("10^"n" "p/c(x)" "p/(x/log(x))" "p/(x/(log(x)1))));
x, pi(x)/c(x), pi(x)/(x/log(x)), pi(x)/(x/(log(x)1))
10^1 2.2583 0.92103 0.52103
10^2 1.6604 1.1513 0.90129
10^3 1.3126 1.1605 0.99250
10^4 1.1296 1.1320 1.0091
10^5 1.0372 1.1043 1.0084
10^6 0.99851 1.0845 1.0060
10^7 0.99447 1.0712 1.0047
10^8 1.0142 1.0613 1.0037
10^9 1.0530 1.0537 1.0029
10^10 1.1086 1.0478 1.0023
10^11 1.1802 1.0430 1.0019
10^12 1.2679 1.0391 1.0015
10^13 1.3725 1.0359 1.0013
10^14 1.4953 1.0332 1.0011
10^15 1.6381 1.0308 1.0010
10^16 1.8030 1.0288 1.0008
10^17 1.9928 1.0270 1.0007
10^18 2.2107 1.0254 1.0006
10^19 2.4604 1.0240 1.0006
10^20 2.7463 1.0227 1.0005
10^21 3.0735 1.0216 1.0005
10^22 3.4479 1.0206 1.0004
10^23 3.8762 1.0196 1.0004
10^24 4.3663 1.0188 1.0004
10^25 4.9273 1.0180 1.0003
With 7 decimals you get enough wiggle room to come close in a small
chosen range, but I'm not impressed by c(x) over a longer range.

Jens Kruse Andersen 0 Attachment
Chris
Yes if you use Excel to compute the 18,435,599,767,349,200,867,866
pairs of values (alpha, beta) your formula
Pi(x) = alpha*x^beta
will give accurate results up to x=10^24. The value of this
exercise escapes me.
Regards
Alan
From: Chris De Corte
Sent: Sunday, July 28, 2013 7:30 AM
To: djbroadhurst ; primenumbers@yahoogroups.com
Subject: Re: [PrimeNumbers] Re: What if Riemann's primecounting formula was not the best?
Please find attached the comparison.
To be more correct, I should also know the pi(x) so that I can finetune my formula as well.
________________________________
From: djbroadhurst <mailto:d.broadhurst%40open.ac.uk>
To: mailto:primenumbers%40yahoogroups.com
Sent: Sunday, July 28, 2013 12:46 PM
Subject: [PrimeNumbers] Re: What if Riemann's primecounting formula was not the best?
 In mailto:primenumbers%40yahoogroups.com,
"chrisdecorte" <chrisdecorte@...> wrote:
> What if Riemann's primecounting formula was not the best?
Perhaps it might be a good idea to find out what Riemann's
formula is? Then try comparing your Excel powerlaw fits
with Gram's convenient version of Riemann's formula, which
you will find in Eq (12) at
http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html
Here is R(10^k) for k = 1 to 10:
R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
for(k=1,10,print([k,round(R(10^k))]))
[1, 5]
[2, 26]
[3, 168]
[4, 1227]
[5, 9587]
[6, 78527]
[7, 664667]
[8, 5761552]
[9, 50847455]
[10, 455050683]
Over to Excel :)
David

Unsubscribe by an email to: mailto:primenumbersunsubscribe%40yahoogroups.com
The Prime Pages : http://primes.utm.edu/
Yahoo! Groups Links
[Nontext portions of this message have been removed]
[Nontext portions of this message have been removed] 0 Attachment
 In primenumbers@yahoogroups.com,
"Jens Kruse Andersen" <jens.k.a@...> wrote:
> So let's make a comparison with exactly computed pi(x) values.
I think that Chris considers "log" to be a complicated function.
> x/log(x) and x/(log(x)1) are the commonly used approximations
> not using li(x) or long formulas.
Here is a perfect fit to Jens' data, without using the dreaded "log":
{data=[4,25,168,1229,9592,78498,664579,5761455,50847534,455052511,
4118054813,37607912018,346065536839,3204941750802,29844570422669,
279238341033925,2623557157654233,24739954287740860,234057667276344607,
2220819602560918840,21127269486018731928,201467286689315906290,
1925320391606803968923,18435599767349200867866,176846309399143769411680];}
Poly=polinterpolate(vector(25,k,10^k),data);
fit(n)=subst(Poly,x,n);
for(k=1,25,print1(fit(10^k)data[k]","));
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
Looks good, to loghaters? Ought to give a good
prediction to pi(10^26), surely :?
print(fit(10.^26));
6.2925202314581568492313228001263868142 E300
Hmm.. Maybe that pesky log function has it uses?
David 0 Attachment
Riemann's (& variant form) primecounting formulas are "the best" in the sense they
yield exact equality. Everywhere.
Given various exact formulas and algorithms for computing pi(x),
the "best" would seem to be the one permitting the fastest computation (maybe memory
consumption should also be taken into account).
And in fact, the fastest currently known algorithm (asymptotically) for computing
pi(x) is based on a form of Riemann, not combinatorial counting methods and not just generating primes. Also, for inexact computation of pi(x) to specified accuracy, this method still seems best known.
However, there is no reason to believe that further speedups are necessarily impossible
with further algorithmic/analytic ideas nobody has thought of yet.
It would help if anybody had the faintest idea how to prove lower bounds on the
computational complexity of counting primes.
I could continue. With GreenTao, we know there are arbitrarily long arithmetic progressions with allprime entries. How computationally complex is it to find an Nterm example? Well... it seems to be extremely hard... quite likely humanity will
never find an example with N=50... but I am unaware of any
reasonable lower bounds, or upper bounds, on this computational complexity! 0 Attachment
Alan,
I said in my document that I only made a calculation up to 49978001 because I don't have other data available.
If you all agree on a new trial then please provide me with 10 N, 10 pi(x) and 10 best Riemann's approximations and I will try to calculate a new alpha and beta.
Best,
Chris
________________________________
From: Alan Powell <AlanPowell@...>
To: primenumbers@yahoogroups.com
Cc: Chris De Corte <chrisdecorte@...>
Sent: Sunday, July 28, 2013 1:42 PM
Subject: Re: What if Riemann's primecounting formula was not the best?
Chris
In the Wikipedia article titled “Primecounting function”
http://en.wikipedia.org/wiki/Primecounting_function%c2%a0
the value of Pi(10^24) is exactly 18,435,599,767,349,200,867,866.
Your “preferred formula”
Pi(x) = alpha*x^beta with alpha=0.2083666 and beta=0.9294465
gives
only 4,222,251,563,919,881,535,488 which is out by a
factor of 4+ !!
You may want to study some elementary books on Number Theory to
understand why Riemann’s function gives the best asymptotic value
as the number of primes tends towards infinity.
Regards
Alan
[Nontext portions of this message have been removed] 0 Attachment
 In primenumbers@yahoogroups.com,
Chris De Corte <chrisdecorte@...> wrote:
> please provide me with 10 N, 10 pi(x) and Â 10 best Riemann's
Please use plain text in messages to this list, else
> approximations and I will try to calculate a new alpha and beta.
you may not be understood. Here I provide
[N, pi(10^N), R(10^N)]
[10, 455052511, 455050683]
[11, 4118054813, 4118052495]
[12, 37607912018, 37607910542]
[13, 346065536839, 346065531066]
[14, 3204941750802, 3204941731602]
[15, 29844570422669, 29844570495887]
[16, 279238341033925, 279238341360977]
[17, 2623557157654233, 2623557157055978]
[18, 24739954287740860, 24739954284239494]
[19, 234057667276344607, 234057667300228940]
[20, 2220819602560918840, 2220819602556027015]
[21, 21127269486018731928, 21127269485932299724]
[22, 201467286689315906290, 201467286689188773625]
[23, 1925320391606803968923, 1925320391607837268776]
[24, 18435599767349200867866, 18435599767347541878147]
[25, 176846309399143769411680, 176846309399141934626966]
where
R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
David 0 Attachment
Hi,
This is the result:
N Pi(x) R(x) Power
10 1E+10 455052511 455050683 420213980
11 1E+11 4118054813 4118052495 3951369042
12 1E+12 37607912018 37607910542 37155635094
13 1E+13 3.46066E+11 3.46066E+11 349383012475
14 1E+14 3.20494E+12 3.20494E+12 3285329105477
15 1E+15 2.98446E+13 2.98446E+13 30892707847616
16 1E+16 2.79238E+14 2.79238E+14 290491262067780
17 1E+17 2.62356E+15 2.62356E+15 2731556383920000
18 1E+18 2.474E+16 2.474E+16 25685455133563200
19 1E+19 2.34058E+17 2.34058E+17 241526262940073000
20 1E+20 2.22082E+18 2.22082E+18 2271127195778980000
21 1E+21 2.11273E+19 2.11273E+19 21355933208335000000
22 1E+22 2.01467E+20 2.01467E+20 200814769003914000000
23 1E+23 1.92532E+21 1.92532E+21 1888307621900430000000
24 1E+24 1.84356E+22 1.84356E+22 17756192398666400000000
25 1E+25 1.76846E+23 1.76846E+23 166965575334147000000000
alpha 0.07774984570
beta 0.9732770961
correlation R(x) 1.00000000000
correlation power 0.999997766
So, yes, Riemann function is better in this test.
I also attach the excel for those who can open it.
I based my testing on a book I was reading about unsolved problems that wrote that Riemann had used the formula x/ln(x) which was obviously an oversimplification.
I am sorry if I wasted your guys day.
Thanks & good night,
Chris
________________________________
From: djbroadhurst <d.broadhurst@...>
To: primenumbers@yahoogroups.com
Sent: Sunday, July 28, 2013 9:11 PM
Subject: [PrimeNumbers] Re: What if Riemann's primecounting formula was not the best?
 In primenumbers@yahoogroups.com,
Chris De Corte <chrisdecorte@...> wrote:
> please provide me with 10 N, 10 pi(x) and Â 10 best Riemann's
Please use plain text in messages to this list, else
> approximations and I will try to calculate a new alpha and beta.
you may not be understood. Here I provide
[N, pi(10^N), R(10^N)]
[10, 455052511, 455050683]
[11, 4118054813, 4118052495]
[12, 37607912018, 37607910542]
[13, 346065536839, 346065531066]
[14, 3204941750802, 3204941731602]
[15, 29844570422669, 29844570495887]
[16, 279238341033925, 279238341360977]
[17, 2623557157654233, 2623557157055978]
[18, 24739954287740860, 24739954284239494]
[19, 234057667276344607, 234057667300228940]
[20, 2220819602560918840, 2220819602556027015]
[21, 21127269486018731928, 21127269485932299724]
[22, 201467286689315906290, 201467286689188773625]
[23, 1925320391606803968923, 1925320391607837268776]
[24, 18435599767349200867866, 18435599767347541878147]
[25, 176846309399143769411680, 176846309399141934626966]
where
R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
David

Unsubscribe by an email to: primenumbersunsubscribe@yahoogroups.com
The Prime Pages : http://primes.utm.edu/
Yahoo! Groups Links
[Nontext portions of this message have been removed] 0 Attachment
 In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:
> Poly=polinterpolate(vector(25,k,10^k),data);
That was, of course, a loglover's spoof on loghaters.
However, this loghater:
http://arxiv.org/pdf/1307.4444.pdf
attempts to fix up the obvious lunacy of polynomial
approximation of pi(x).
Andrey Kulsha may offer us tighter conjectural
bounds on pi(10^26) ?
David 0 Attachment
 In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:
> Andrey Kulsha may offer us tighter conjectural
On the assumption that Delta(x) defined by Andrey in
> bounds on pi(10^26) ?
http://www.primefan.ru/stuff/primes/table.html#theory
continues to satisfy abs(Delta(x)) < 1, I estimate that
pi(10^26) = 1699246750872419991992147 +/ 167036339194
David (subject to error, as ever) 0 Attachment
djbroadhurst wrote:>>
........
> [N, pi(10^N), R(10^N)]
> [25, 176846309399143769411680, 176846309399141934626966]
For large values of x, this algorithm is inconvenient, eg for x = 10^250 requires over 1868 terms,
>
> where
>
> R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
>
Much faster can be calculated as
pi(x) ~= pli(x) = round(Li(x)  1/2 Li(sqrt(x)))
where Li(x) is the Logarithm integral
pli(10^25) = 176846309399141938590795
(pli(10^25)/R(10^25))  1 = 2 10^17
(pli(10^25)/pi(10^25)) 1 = 1 10^14
pli{10^250)= 1740206254656916846774941665048386410178028975968929264655269395003484\
7365084787720410883002915274182213664956284195372937010842285191263145\
7678993892420170619475710388189158537825404886895382231933346054713467\
85875358018952542776800464839768387582

marian otremba 0 Attachment
 In primenumbers@yahoogroups.com,
Chroma <chromatella@...> wrote:
>> R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
No. The Gram formula is still very convenient at this size.
> For large values of x, this algorithm is inconvenient,
> eg for x = 10^250 requires over 1868 terms
PariGP, gives the exact value of R(10^250) in 0.1 seconds:
R(x)=round(1+suminf(k=1,log(x)^k/(zeta(k+1)*k*k!)));
{default(realprecision,260);print(R(10^250));
print(" took "gettime" milliseconds");
17402062546569168467749416650483864101780289759689292646552693950034847365084787720410883002915274182213664956284195372937010842285191263145767899389242017061947571038442681072462756632213511422607548574658029047365218974809766827365028215685475746
took 98 milliseconds
Perhaps you are paying for inferior software?
If so, the general rule is: the less you pay,
the better the deal.
PariGP is totally free and hence rather hard to beat :)
David
Your message has been successfully submitted and would be delivered to recipients shortly.