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

Author

Hugo Pfoertner, Sep 16 2004

Keywords

• nonn

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

Examples

			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
		

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.

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).

Programs

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 *)

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

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.