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
KEYWORD
nonn
AUTHOR
Hugo Pfoertner, Sep 16 2004
STATUS
approved