Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • cino hilliard
    Hi, A while ago I determined sum of primes
    Message 1 of 8 , Jul 30, 2009
    • 0 Attachment
      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

      about 10 times better yet.



      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]
    • David Broadhurst
      ... Euler-Maclaurin David
      Message 2 of 8 , Jul 30, 2009
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        cino hilliard <hillcino368@...> wrote:

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

        Euler-Maclaurin

        David
      • David Broadhurst
        ... 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, 2009
        • 0 Attachment
          > --- In primenumbers@yahoogroups.com,
          > 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
        • Cino Hilliard
          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 9:42 AM
          • 0 Attachment
            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

            --- In primenumbers@yahoogroups.com, "David Broadhurst" <d.broadhurst@...> wrote:
            >
            > > --- In primenumbers@yahoogroups.com,
            > > 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
            >
          • David Broadhurst
            ... http://physics.open.ac.uk/~dbroadhu/cert/eulmac.gp David
            Message 5 of 8 , Aug 7 10:47 AM
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              "Cino Hilliard" <hillcino368@...> wrote:

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

              http://physics.open.ac.uk/~dbroadhu/cert/eulmac.gp

              David
            • David Broadhurst
              ... 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 12:19 AM
              • 0 Attachment
                --- In primenumbers@yahoogroups.com,
                "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
              • Cino Hilliard
                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 11:13 PM
                • 0 Attachment
                  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.

                  David Broadhurst wrote:
                  > 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
                • David Broadhurst
                  ... 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 2:34 AM
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com,
                    "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.

                    Glad to help.

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