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
>Subject: Re: sum of first 10^n primes A099824
>Date: Wed, 4 Oct 2006 08:42:51 -0700
>
>On 10/4/06, cino hilliard <hillcino368 at hotmail.com> wrote:
>
>> >>%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?
>
>No, I did not. I believed that prime() behaved like an array (in which
>case it would be much faster than nextprime()).
>
>>(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()
>
>Oh, that's surprising. Could you also try the following program:
>
>sumprimes2(n) = local(s);s=0;forprime(p=2,prime(n),s+=p);s

That is much faster than using prime(x) or nextprime(x)  but again, breaks 
down at n=10^8.
Depeding on what one is doing, one could use this and switch to nextprime 
after n > 203 mill.
One could post an inquiry at the Pari List to see why forprime wins the 
race. My guess is that
since there are pi(x) primes less than n or far less than n, foreprime only 
selects these
one at a time while prime(n) address all of n. Here they are using an 
indexed list or an array.
Maybe someone here knows the inner workings.

I have always try to  use forprime in my scripts simply because it is to kin 
to for and logical.

Enjoy,
Cino