tables of p(n) and/or pi(n) / tables of primes

[cino hilliard]

>From: Hans Havermann <pxp at rogers.com>
>To: seqfan at ext.jussieu.fr
>Subject: Re: tables of p(n) and/or pi(n) / tables of primes
>Date: Mon, 19 Sep 2005 11:26:57 -0400
>
>On Sep 19, 2005, at 6:53 AM, cino hilliard wrote:
>
>>I have computed and stored all primes < 100 billion in a 45 gig file.
>
>How much extra time would the base conversion/compression add to  accessing 
>the database for real-time arithmetic? For example, how  long would it take 
>you to sum the first billion primes?



Here are some timings for powers of 10

Start => 1
End   => 10

129  0.000000   Sec
Start => 1
End   => 100

24133  0.000000   Sec
Start => 1
End   => 1000

3682913  0.016000   Sec
Start => 1
End   => 10000

496165411  0.078000   Sec
Start => 1
End   => 100000

62260698721  0.844000   Sec
Start => 1
End   => 1000000

7472966967499  8.734000   Sec
Start => 1
End   => 10000000

870530414842019  90.359000   Sec
Start => 1
End   => 100000000

99262851056183695  916.297000   Sec
1Start => 1
End   => 1000000000

11138479445180240497  9618.172000   Sec

This agrees with A099824.

This last timing  is a little high as I set priority to low and did a lot of 
other work on this processor.

Pari and Maple times are abismal. I don't have Mathematica.

g(n) = s=0;for(j=1,n,s+=prime(j));print(s)

(18:03) gp > g(100000)
62260698721
time = 12,750 ms.
%31 = 0
(18:04) gp > g(200000)
264129169599
time = 50,485 ms.
%32 = 0
(18:05) gp > g(400000)
1116583315953
time = 3mn, 20,344 ms.

It has been said that it is futile to try to "look-up" primes vs compute 
them because the processor
is so fast these days with a sieve. I don't believe it. This demo proves we 
can beat any processor by
loo-kup.  If we go from HD to solid state drives we can do even better.  Of 
course we must be
humble to explain how much time we spent to build the table. Indeed, it is 
taking me about 2 days
to do  primes between 100+x bill  to 100+x+5 bill. So to get to  200 billion 
it will take 20*2 = 40
days. 40*10 = 400 days. so next year I will extend A099824 by 1 term. :-)

However, isprime(x) may be a different matter. The only way a table will 
help here is with a binary
search. Perhaps we can prove that a look-up cannot be as fast no matter how 
big the table is.
Eg., for a table of the first 1 trillion primes we will need to do at most 
40 iterations to find if
a selected number is in the table. prime(1e12) = 29996224275833 anf Pari 
ispseudoprime figures
it out in less than 1/1000 ms. Looking it up with a binary search would 
probably take a lot longer.

There has to be a theory that addresses this.

Have fun,
Cino