## Sum of x/log(x) x=2..n

Expand Messages
• Hi, A while ago I determined sum of primes
Message 1 of 8 , Jul 30 2:24 AM
Hi,

A while ago I determined sum of primes < n approximates
the number of primes < n^2. This implies that we can approximate
Pi(n) by simply adding primes < sqrt(n). Look mom, no logs!

We know Pi(x) ~ x/log(x) ~ x/(log(x)-1) where the last statement
is much more accurate.

Attempting to get something in closed form, I tried summing

x/log(x) x=2..10^n and noticed that this gives a much better
approximation to the number of primes < 10^(2n)

For example,

sum of primes < 10^9 = 24739512092254535

sum(x=2,10^9,x/log(x) = 24739954333817884

Pi(10^18) = 24739954287740860

Very good but it takes Pari on a 2.53 ghz 3 hours to sum.

Now the logarithmic integral Li(n) = int(x=2..n,dx/log(x))

Li(10^18) =24739954309690415

This is a slightly better approximation. The urge is almost irresistible to

say these two concepts imply each other. With one we can avoid the
calculus though.

Rg(10^18) = 24739954284239494 (Riemann-Gram approx of Pi(x) is

Having had the great success with summing x/log(x), naturally it would

follow summing x/(log(x)-1) would give even better results. Right? Wrong.

Strange indeed.

Anyway, I am looking for a faster calculation for x/log(x). At this rate,

it will take 125 days for n = 10^12. Currently, I am using the trick

sum(x=2,5*10^9,x/log(x))

sum(x=5*10^9+1,10^10,x/log(x))

in 2 pari sessions on dell gx620 3.2 ghz vista 64 to compute the sum for
n = 10^10 with Gimps is running in the background.

Enjoy,

Cino

[Non-text portions of this message have been removed]
• ... Euler-Maclaurin David
Message 2 of 8 , Jul 30 2:47 AM
cino hilliard <hillcino368@...> wrote:

> I am looking for a faster calculation for x/log(x).

Euler-Maclaurin

David
• ... Euler-Maclaurin gave these results in less than a second: [ k, sum(x=2,10^k,x/log(x))] [ 9, 24739954333817884.765108796387854980062067356675901] [10,
Message 3 of 8 , Jul 30 4:39 AM
> cino hilliard <hillcino368@> wrote:
> I am looking for a faster calculation for x/log(x).

Euler-Maclaurin gave these results in less than a second:

[ k, sum(x=2,10^k,x/log(x))]

[ 9, 24739954333817884.765108796387854980062067356675901]
[10, 2220819603000810723.0256382787068599092733377762963]
[11, 201467286693222327323.50889662513497938846705904284]
[12, 18435599767384443378555.311612011169981547316897585]
[13, 1699246750872760069344915.8741205160589367732107901]
[14, 157589269275976389210121053.30825414331084987218682]
[15, 14692398897720462115561817776.152711329547881311518]
[16, 1376110866993766140634547918278.2822391520225219083]
[17, 129408626505158943971865401935043.41415238141439346]
[18, 12212914297619365466978260828820202.579301156342592]
[19, 1156251261026516898232106385426821880.5658457303344]
[20, 109778913489828302829174401609875888501.15351452821]
[21, 10449550362264587535492180923467208556377.216140121]
[22, 996973504768769817629382023798067858752836.80045752]

615 milliseconds

David
• Ok David, I give up. I searched and I searched and cannot find an interpretable (by me) routine I can convert to Pari or c/gmp. I can t afford Mathematica even
Message 4 of 8 , Aug 7, 2009
Ok David, I give up.

I searched and I searched and cannot find an interpretable (by me)
routine I can convert to Pari or c/gmp.

I can't afford Mathematica even at \$295.

How did you do it?

I want to examine

sm(m,n)=sum(x=m,n,x/log(x)-1/log(x)+a/log(x)^2-b/log(x)^3)
for various values of m and n and hone in on a and b using
known tables of Pi(x) and the approx R(x).

a=1,b=1 m=2 gives pretty good approximations of Pi(n^2),
about 1/2 the digits. Also it seems this is as good as
Li(x).

Are they asymptotic?

It seems to me that the simple act of adding prime numbers
and then noticing that the sum of these primes up to some
number n is quite close to the count of the primes less than
n^2 or Pi(n^2) should have been discovered hundreds of years
ago.

There should be a word for this. Often, knowledge replaces
simple truths that lay hidden which much later are discovered
with more knowledge.

Basically, we always had a good approximation of Pi(x) by the
simple operations of a sieve and addition. Somehow, the invention
of natural logarithms provided the knowledge for a 15 year old (I
doubt this and the add 1 to 100 story) to just start experimenting
with a table of logs finding the log of a number and a count of
primes from tables of primes. Had he not known logs, he may have
experimented with the sum of the primes less than n in the tables
of primes. After listing the sums, he then may have noticed that
sum of prime < n ~ count of primes < n^2 which for large n,is a
much better estimate of Pi(x) than x/(log(x)-1).

For example,
Pi(10^22) = 201467286689315906290
SumP(sqrt(10^22)) = 201467077743744681014
10^22/(log(10^22)-1) = 201381995844659893517.7646894

In 1817 tables of primes grew to around less than 3 million. Too
bad the table builders did not accumulate the primes as they built the tables.

Nevertheless, my guess is a Savant could have accumulated the sums
of the first 216,816 primes in a short time. Evan a couple of 8th
grade classes could have done it in a few days. This is an example
of an almost free lunch. A little addition early closely predicts
a later truth.

Per is summa nos victum,

Cino

>
> > cino hilliard <hillcino368@> wrote:
> > I am looking for a faster calculation for x/log(x).
>
> Euler-Maclaurin gave these results in less than a second:
>
> [ k, sum(x=2,10^k,x/log(x))]
>
> [ 9, 24739954333817884.765108796387854980062067356675901]
> [10, 2220819603000810723.0256382787068599092733377762963]
> [11, 201467286693222327323.50889662513497938846705904284]
> [12, 18435599767384443378555.311612011169981547316897585]
> [13, 1699246750872760069344915.8741205160589367732107901]
> [14, 157589269275976389210121053.30825414331084987218682]
> [15, 14692398897720462115561817776.152711329547881311518]
> [16, 1376110866993766140634547918278.2822391520225219083]
> [17, 129408626505158943971865401935043.41415238141439346]
> [18, 12212914297619365466978260828820202.579301156342592]
> [19, 1156251261026516898232106385426821880.5658457303344]
> [20, 109778913489828302829174401609875888501.15351452821]
> [21, 10449550362264587535492180923467208556377.216140121]
> [22, 996973504768769817629382023798067858752836.80045752]
>
> 615 milliseconds
>
> David
>
Message 5 of 8 , Aug 7, 2009
"Cino Hilliard" <hillcino368@...> wrote:

> Ok David, I give up.
>
> How did you do it?

David
• ... f(x,lx) = x/lx - 1/lx + a/lx^2 - b/lx^3; modify at will a=1; b=1; m=2; chosen values p50 terms=10;trunc=10^4;g=f(x,lx);d=[];bv=bernvec(terms+1);
Message 6 of 8 , Aug 8, 2009
"Cino Hilliard" <hillcino368@...> wrote:

> I want to examine
> sm(m,n)=sum(x=m,n,x/log(x)-1/log(x)+a/log(x)^2-b/log(x)^3)
> a=1,b=1,m=2

f(x,lx) = x/lx - 1/lx + a/lx^2 - b/lx^3; \\ modify at will
a=1; b=1; m=2; \\ chosen values

\p50
terms=10;trunc=10^4;g=f(x,lx);d=[];bv=bernvec(terms+1);

{for(n=1,2*terms-1, \\ store odd derivatives
g=deriv(g,x)+1/x*deriv(g,lx);if(n%2,d=concat(d,g)));}

fx(x)=f(x,log(x));
dx(y)=subst(subst(d,x,y),lx,log(y));

{emac(m,n)=local(dm,dn);
dm=dx(m);dn=dx(n);intnum(x=m,n,fx(x))+(fx(n)+fx(m))/2
+sum(k=1,terms,bv[k+1]/((2*k)!)*(dn[k]-dm[k]));}

s=sum(k=2,trunc-1,fx(k));

{sm(m,n) = \\ as requested
if(n>trunc&&trunc>m&&m>1,s-sum(k=2,m-1,fx(k))+emac(trunc,n));}

for(k=10,22,print([k,sm(m,sqrtint(10^k))]))

realprecision = 57 significant digits (50 digits displayed)
[10, 455051173.78013348859945302791104662093667330309988]
[11, 4118034570.4638268343263084222227560024582402009128]
[12, 37607913583.517014991610186636613681414323919745603]
[13, 346065399465.03248684994266161913298076743032790216]
[14, 3204941752475.7266213978929589359007763992788467339]
[15, 29844569450368.625194208305114011697818820369920647]
[16, 279238341514801.87986838501363369093160129071417051]
[17, 2623557157209703.2566630532132281009952796686474077]
[18, 24739954285430064.167128134429584525396645626800130]
[19, 234057667279245072.15948934429135642246573100181670]
[20, 2220819602565566257.9962162533153260118661266449421]
[21, 21127269485065195786.472528704950924409440892097567]
[22, 201467286689267167012.50527750985870920146256019519]

Comment: This is an inefficient method of fiddling with Li(x).
Cino is trying to avoid integration. Yet it is needed for
Euler-Maclaurin summation.

David
• Hi David, You did a lot of work here to develop emac(m,n).I appreciate it as it saved me a lot of time and possibly money. Thank you. ... Maybe. Anyway I don t
Message 7 of 8 , Aug 8, 2009
Hi David,
You did a lot of work here to develop emac(m,n).I appreciate
it as it saved me a lot of time and possibly money.
Thank you.

> Comment: This is an inefficient method of fiddling with Li(x).

Maybe. Anyway I don't mind inefficiencies as I have to use them
everyday like the QWERTY keyboard and all the right handed stuff
around for this lefty.

Surprizingly, the most efficient combination in the real world for moving a mass from point A to point B with the least expenditure
of energy, is a human riding a bicycle on a flat surface. Then
there is the hummingbird which is one of the the least efficient systems that has been around for a while.

Nevertheless, Your emac(m,n) gets good mileage and is more
accurate than Li(x) =-eint1(log(1/x)) and
li(x,n) = lg=log(x);x*sum(k=1,n,(k-1)!/lg^k)

gp > p23=1925320391606818006727
gp > em23=emac(2,sqrt(10^23))
%116 = 1925320391608063705941.14436225628
gp > Li23=Li(10^23)
%117 = 1925320391614054155138.78012956636
gp > R23=R(10^23)
%118 = 1925320391607837268776.09905063742
gp > 1-em23/p23
%122 = -6.4700878855011600657703221947361 E-13
gp > 1-Li23/p23
%123 = -3.7584125963269129092185767109212 E-12
gp > 1-R23/p23
%124 = -5.2939866712178918250597351383218 E-13

For 10^22, emac is better than R(x).

The actual sum of the primes < sqrt(n) ~ Pi(n) is not as
accurate as emac but it is quite good wit RE below.

For sum of primes < 10^n, See the b-file at
http://www.research.att.com/~njas/sequences/A046731

sump11 = 201467077743744681014
gp > p22 = 201467286689315906290
%137 = 201467286689315906290
gp > 1. - sump11/p22
%139 = 0.00000103711..
This is magnitudes better than RE of 10^22/log(10^22)-1) =
0.000423348356239

I find this sum of primes <= sqrt(n) ~ primes <= n to be an
amazing property of prime numbers and the integers.

Bottomline, thanks to David, we have an eulermac function in
Pari.

Cheers and Roebuck,
Cino
• ... Glad to help. ... Not so amazing when you realize that the integrals I1(N) = intnum(x=2, sqrt(N), x/log(x)) I2(N) = intnum(y=2, N , 1/log(y)) differ
Message 8 of 8 , Aug 9, 2009
"Cino Hilliard" <hillcino368@...> wrote:

> Hi David,
> You did a lot of work here to develop emac(m,n).
> I appreciate it as it saved me a lot of time and
> possibly money. Thank you.

> I find this sum of primes <= sqrt(n) ~ primes <= n to be
> an amazing property of prime numbers and the integers.

Not so amazing when you realize that the integrals

I1(N) = intnum(x=2, sqrt(N), x/log(x))
I2(N) = intnum(y=2, N , 1/log(y))

differ only by a constant, no matter what the value of N.

Proof: Transform the latter by setting y = x^2. Then
I2(N) - I1(N) = - I1(2) = 1.92242131492155809316615998937951547...

David
Your message has been successfully submitted and would be delivered to recipients shortly.