sum of first 10^n primes A099824

[cino hilliard]

Hi Max,

>From: "Max A." <maxale at gmail.com>
>To: "cino hilliard" <hillcino368 at hotmail.com>
>CC: seqfan at ext.jussieu.fr, yahoogroups.seqfun at yahoo.com
>Subject: Re: sum of first 10^n primes A099824
>Date: Wed, 4 Oct 2006 01:31:02 -0700
>
>On 10/3/06, cino hilliard <hillcino368 at hotmail.com> wrote:
>
>>Because we can compute the sums of primes in ranges, group efforts with
>>several computers
>>could be used to attain sums of the first pi(10^15) primes.
>
>It may happen that the Meissel, Lehmer, Lagarias, Miller, Odlyzko
>algorithm for computing pi(x)
>( see http://www.ams.org/journal-getitem?pii=S0025-5718-96-00674-6 and
>http://numbers.computation.free.fr/Constants/Primes/countingPrimes.ps
>)
>can be adapted to computing the sum of first n primes. That
>potentially may speed up things a lot (e.g., pi(10^n) is known for n
>up to 22).

Yes that is true but it is a single bound. In a computation of prime(x) you 
would need all
sequential values of pi(x) betwreen 10^0 to 10^22 to be useful for computing 
prime(x).

>
>>The simple Pari program below will compute the sum of the first 10^11 
>>primes
>>in about 21 days. Someone may want to verify this with Pari.
>
>[...]
>
>>%o A099824 (PARI) sumprimes(n) = a=1;sum(x=1,n,a=nextprime(a+1))
>
>PARI/GP can do faster than that. One needs just to run gp with an
>appropriate parameter -p, and then define sumprimes simply as
>sumprimes(n) = sum(x=1,n,prime(x))
>sumprimesmax(n) = sum(x=1,n,prime(x))

Did you test sumprimes(n) = sum(x=1,n,prime(x)) for timing? Maybe you are 
using
gp2c?

(05:19:13) gp > sumprimesmax(10^5)
time = 4,828 ms.
%274 = 62260698721
(05:19:23) gp > sumprimescino(10^5)
time = 750 ms.
%275 = 62260698721
(05:19:42) gp >

So using nextprime() is about 4828/750 = 6.44 times faster than using 
prime()

Besides that the primelimit of pari is  primes < 4.29 billion, the number of 
primes < 4.29 bill
is    203056468 ~ 2*10^8. So even if prime(x) was infinitely faster than 
nextprime, we would
not be able to compute the sum for the first 10^9 primes. using nextprime it 
takes about 4
hours to compute the first 10^9 primes..

Pari stores differences of primes in their table and computes prime(x) from 
that. It would be
much faster if they stored the primes in 8 byte binary. This would eat 1.6 
gigs for the current
limit but would ooo so fast!

Using the sieve program  you can store all primes < 1 trillion in 8 byte 
binary in a file just over
300 giga bytes in about 20 hours. Then reading this file you can sum the 
first 10^10 primes faster
than any other method. I call this file from a pari script prime2(n). It is 
slower tham prime(n) but
takes me to primes < 1 trillion in the pari environment.

For example, the sieve I provided takes 7860 sec to sum the first 10^9 
primes while reading the
file takes 1984 sec.

Of course if this is all you want to do the sieve is much faster since it 
took 20 hours to create the
file. However, if you wanr to anaylize first 2^n, 3^n, 4^n, sums of twins, 
cousins, sexy etc
a saved file will eventially swamp any calculation on the fly method.

We can increase the number of primes in our file by using wheels 30k+r, 
210k+r, 2310k+r etc
and further reduce our storage allowing us to store primes < 10^15 in 300 
gigs. Of course this
will cost in calculating the records of the file.


Once this is done we can quickly look up pi(x).  But with the file we don 
need pi(x) since each
record in the file is an index for a prime. It is just a matter of pointing 
the record and read the
file to get the prime.

What I am saying here is simply that the best formula for prime numbers is 
storage! Ain't no way
around it once you have sieved to get the storage.

Have fun
Cino