

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 70MByte file.
Because of divisibility by 7, 254 appears only as the zeroth term, and 127 and 255 do not appear at all. All other singlebyte 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 << (i1)))); } \\ 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 (7rough 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



