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.

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

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
(Python)
from sympy import isprime
v = [1, 7, 11, 13, 17, 19, 23, 29]
def a(n): return sum(2**k for k, vk in enumerate(v) if isprime(n*30+vk))
print([a(n) for n in range(1, 58)]) # Michael S. Branicky, Oct 10 2021

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: A345533 A345785 A359449 * A138665 A271799 A152824

Adjacent sequences: A098588 A098589 A098590 * A098592 A098593 A098594

Keyword

nonn

Author

Hugo Pfoertner, Sep 16 2004

Status

approved