login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A098591 a(k) contains primality information for the numbers in the interval (k*30,...,(k+1)*30) packed into one byte using the fact that only numbers == 1, 7, 11, 13, 17, 19, 23, 29 mod 30 can be prime. 3
223, 239, 126, 182, 219, 61, 249, 213, 79, 30, 243, 234, 166, 237, 158, 230, 12, 211, 211, 59, 221, 89, 165, 106, 103, 146, 189, 120, 30, 166, 86, 86, 227, 173, 45, 222, 42, 76, 85, 217, 163, 240, 159, 3, 84, 161, 248, 46, 253, 68, 233, 102, 246, 19, 58, 184, 76 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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

Because of divisibility by 7, 254 appears only as the zeroth term, and 127 and 255 do not appear at all. All other single-byte numbers (0..255) appear. 247 is the last to appear, first appearing as the 22621st term.

0 and at least one nonzero term must both appear infinitely often. (Probably every number 0..126 and 128..253 appears infinitely often, but this may be hard to prove.) - Keith F. Lynch, Sep 09 2018

LINKS

Michael De Vlieger, Table of n, a(n) for n = 1..10000

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.

FORMULA

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

EXAMPLE

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) and 523 == 13 (mod 30). Therefore a(17) = 2^2 (representing 510 + 11) + 2^3 (representing 510 + 13) = 4 + 8 = 12.

a(360) = 0 (1st occurrence), no primes between 360*30 = 10800 and 10830. - Frank Ellermann, Apr 03 2020

MATHEMATICA

With[{s = Select[Range@ 30, CoprimeQ[#, 30] &]}, Array[Total[2^(Position[30 # + s, _?PrimeQ][[All, 1]] - 1) ] &, 57]] (* Michael De Vlieger, Sep 10 2018 *)

PROG

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.

(PARI) a(k) = {vec = [1, 7, 11, 13, 17, 19, 23, 29]; return (sum(i=1, length(vec), isprime(30*k+vec[i])*(1 << (i-1)))); } \\ Michel Marcus, Jan 31 2013

CROSSREFS

Cf. A000040 (prime numbers), A006880 (number of primes < 10^n), A098592 (number of primes in intervals (30*k, 30*(k+1))), A005867 (primorial sieving candidates), A007775 (7-rough numbers, corresponding to the bits).

Sequence in context: A092623 A220474 A243767 * A138665 A271799 A152824

Adjacent sequences:  A098588 A098589 A098590 * A098592 A098593 A098594

KEYWORD

nonn

AUTHOR

Hugo Pfoertner, Sep 16 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 13 13:48 EDT 2020. Contains 335688 sequences. (Running on oeis4.)