1,1

This sequence illustrates an efficient method to store all prime numbers up to some moderate limit. With this method all prime numbers < 2^31 can be stored in a 70 MByte file.

Hugo Pfoertner, Generation of a file with packed primes. FORTRAN program.

Hugo Pfoertner, Primality testing using a packed lookup table. FORTRAN program.

Hugo Pfoertner, Programs to generate and access a packed prime lookup table. Executable programs and source code..

a(n)=sum_{k=0..7} (2^k)*isprime(30*n+offset(k)), where isprime(x)=1 for x prime, else 0, and offset(k)={1, 7, 11, 13, 17, 19, 23, 29} for k=0, .., 7.

a(1)=223: From the list of prime candidates between 30 and 60 only the number 49 is composite. Therefore a(1)=2^0 (representing 30+1) + 2^1 (representing 30+7) + 2^2 (representing 30+11) + 2^3 (representing 30+13) + 2^4 (representing 30+17) + 2^6 (representing 30+23) + 2^7 (representing 30+29) = 1+2+4+8+16+64+128 = 223.

a(17): There are 2 primes in the interval (17*30,17*30+30)=(510,540): 521=11 mod 30, 523=13 mod 30. Therefore a(17)=2^2 (representing 510+11) + 2^3 (representing 510+13) = 4+8=12.

Links to FORTRAN source code and executable programs to create the resulting binary file and to use it for extremely fast primality testing are provided.

Cf. A000040 prime numbers, A006880 number of primes < 10^n, A098592 number of primes in itervals (30*k, 30*(k+1)).

Sequence in context: A105982 A100607 A092623 this_sequence A142386 A102950 A118818

Adjacent sequences: A098588 A098589 A098590 this_sequence A098592 A098593 A098594

nonn

Hugo Pfoertner (hugo(AT)pfoertner.org), Sep 16 2004