|
%I #72 Jan 23 2023 09:08:35
%S 223,239,126,182,219,61,249,213,79,30,243,234,166,237,158,230,12,211,
%T 211,59,221,89,165,106,103,146,189,120,30,166,86,86,227,173,45,222,42,
%U 76,85,217,163,240,159,3,84,161,248,46,253,68,233,102,246,19,58,184,76
%N 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.
%C 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.
%C 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.
%C 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
%H Michael De Vlieger, <a href="/A098591/b098591.txt">Table of n, a(n) for n = 1..10000</a>
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/packsv.for">Generation of a file with packed primes.</a> FORTRAN program.
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/prime.for">Primality testing using a packed lookup table.</a> FORTRAN program.
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/packsv.zip">Programs to generate and access a packed prime lookup table.</a> Executable programs and source code.
%F 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.
%e a(1)=223: From the list of prime candidates between 30 and 60 only the number 49 is composite. Therefore
%e a(1) = 2^0 (representing 30 + 1)
%e + 2^1 (representing 30 + 7)
%e + 2^2 (representing 30 + 11)
%e + 2^3 (representing 30 + 13)
%e + 2^4 (representing 30 + 17)
%e + 2^6 (representing 30 + 23)
%e + 2^7 (representing 30 + 29)
%e = 1 + 2 + 4 + 8 + 16 + 64 + 128 = 223.
%e 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.
%e a(360) = 0 (1st occurrence), no primes between 360*30 = 10800 and 10830. - _Frank Ellermann_, Apr 03 2020
%t With[{s = Select[Range@ 30, CoprimeQ[#, 30] &]}, Array[Total[2^(Position[30 # + s, _?PrimeQ][[All, 1]] - 1) ] &, 57]] (* _Michael De Vlieger_, Sep 10 2018 *)
%o 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.
%o (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
%o (Python)
%o from sympy import isprime
%o v = [1, 7, 11, 13, 17, 19, 23, 29]
%o def a(n): return sum(2**k for k, vk in enumerate(v) if isprime(n*30+vk))
%o print([a(n) for n in range(1, 58)]) # _Michael S. Branicky_, Oct 10 2021
%Y 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).
%K nonn
%O 1,1
%A _Hugo Pfoertner_, Sep 16 2004
|
