-----Original Message-----
From: cino hilliard [mailto:hillcino368@hotmail.com] 
Sent: Wednesday, September 21, 2005 01:47
To: seqfan@ext.jussieu.fr
Cc: cinohill@hotmail.com
Subject: Re: tables of p(n) and/or pi(n) / tables of primes

>From: Hans Havermann <pxp@rogers.com>
>To: seqfan@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?


Cino's timings (which processor & speed?)

>Here are some timings for powers of 10
[...]
> Start => 1
> End   => 1000000
> 7472966967499  8.734000   Sec
>
> Start => 1
> End   => 10000000
> 870530414842019  90.359000   Sec
>
> Start => 1
> End   => 100000000
> 99262851056183695  916.297000   Sec
>
> Start => 1
> End   => 1000000000
> 11138479445180240497  9618.172000   Sec
>
>This agrees with A099824.

During the "Primal Squares" Programming Contest
http://www.recmath.org/contest
(this was the one for which there was a request for problems some months ago
in our group)
I used a 333Mbyte binary table to decide primality for numbers<10^10. Such a
table, which uses the "classical" 30 numbers/byte technique is easily kept
in memory. For examples and source code see:
http://www.research.att.com/projects/OEIS?Anum=A098591
On the machines I used (SGI Altix under Linux with Intel Itanium2
processors) this table remained in the memory file cache after the first
start of a program using this table. Reading the table for the first time
from disk takes aprox. 11 secs, subsequent loading of the table when a
program using the table is started again takes less than 1 sec.

Summing the first 10^6 primes takes 0.57s CPU, 10^7 primes 4.28s CPU and the
10^8 primes sum takes 45.67s CPU, which is roughly 20 times faster than
Gino's timings. Of course the results are identical with Gino's.

The program just runs through a loop over all odd numbers x calling the
function "jsprim(x)", and stops after enough primes are found. The (Fortran)
function jsprim should be easily translatable in any other programming
language:

      logical function jsprim ( z )
C Check for primality using compressed table of precomputed primes
C Author: Hugo Pfoertner hppt://www.pfoertner.org/
C
C Change history:
C Jun 23 2004 Data type of input set to integer*8
C Sep  3 2004 initial version
C
      implicit integer (a-z)
      parameter (ip=333333333,msmalp=31)
C
      integer*8 z
      integer k, map(0:29)
      integer*1 mk, pckdp(0:ip)
      common /packpr/ pckdp
      logical smlpri(0:msmalp)
C
      data map / -1,
     &   0, -1, -1, -1, -1, -1,  1, -1, -1, -1,
     &   2, -1,  3, -1, -1, -1,  4, -1,  5, -1,
     &  -1, -1,  6, -1, -1, -1, -1, -1,  7 /
      data smlpri /.false.,.false.,.true.,.true.,.false.,.true.,
     &                     .false.,.true.,.false.,.false.,.false.,
     &                     .true.,.false.,.true.,.false.,.false.,
     &                     .false.,.true.,.false.,.true.,.false.,
     &                     .false.,.false.,.true.,.false.,.false.,
     &                     .false.,.false.,.false.,.true.,.false.,
     &                     .true. /
C Start of test
C Special treatment for small numbers
      if ( z .le. msmalp ) then
C Look into table
        jsprim = smlpri(z)
      else
C determine location of relevant byte
        j = z / 30
C relative position in byte
        k = z - 30 * j
C Map to bits carrying information
        mk = map(k)
C standard locations for composites
        if ( mk .lt. 0 ) then
          jsprim = .false.
        else
C use pre-computed table values
          jsprim =  btest(pckdp(j),mk)
        endif
      endif
      return
C End of logical function JSPRIM
      end

-------------------------------------------
Some remarks on the programming contest:

Congratulations to Joshua Zucker, who performed better than I did in the
contest, especially because he probably didn't have my computer resources.

Before the contest I had submitted
http://www.research.att.com/projects/OEIS?Anum=A109943
in which a(3)=37 is wrong. I've submitted a corrected and extended version
1,11,30,63,116,187,281

I'll also submit the first terms of the part 2 contest scores:
http://www.recmath.org/contest/description.php and
http://www.recmath.org/contest/BestSolutions2.php

which make the sequence (starting at n=1)

2 21 72 181 390 715 ...

1192 1847 are lower bounds for the next terms a(7) and a(8)

a(2)=21 is the "part 2"  score for the matrix
4 7
3 1
which contains two single digit primes and one even number (score:2+1)
and 9 2-digit primes: 13,17,31,37,41,43,47,71,73 score(9*2); total=3+18=21


Hugo Pfoertner

===========================================================================
REFERENCE of the administration: This E-Mail was delivered via InterNet.
Unencrypted InterNet-E-Mails could be read or falsified by unauthorized
persons.
---------------------------------------------------------------------------
HINWEIS der Administration: Diese E-Mail wurde Ihnen ueber INTERNET
zugestellt. Unverschluesselte Internet-E-Mails koennten von Unbefugten
gelesen oder verfaelscht werden.
===========================================================================




