A153352 K-bit primes p such that p-2^i and p+2^i are composite for 0<=i<=K-1.

1973, 3181, 3967, 4889, 8363, 8923, 11437, 12517, 14489, 19583, 19819, 21683, 21701, 21893, 22147, 22817, 24943, 27197, 27437, 28057, 29101, 34171, 34537, 34919, 35201, 35437, 36151, 38873, 41947, 42169, 42533, 42943, 43103, 43759

Offset

1,1

Comments

Sun showed that the sequence is of positive density in the primes; in particular, of relative density >= 7.9 * 10^-29 = 1/phi(66483034025018711639862527490).

Terry Tao gives this sequence explicitly (p. 1) and generalizes Sun's result.

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Fred Cohen and J. L. Selfridge, Not every number is the sum or difference of two prime powers, Math. Comput. 29 (1975), pp. 79-81.

Zhi-Wei Sun, On integers not of the form +-p^a +- q^b, Proceedings of the American Mathematical Society 128:4 (2000), pp. 997-1002.

Terence Tao, A remark on primality testing and decimal expansions, Journal of the Australian Mathematical Society 91:3 (2011), pp. 405-413.

Terence Tao, A remark on primality testing and the binary expansion (blog entry)

Example

a(1)=1973 because 1973 has 11 bits, and 1973 +-1, 1973 +-2, 1973 +-4, 1973 +-8, 1973 +-16, 1973 +-32, 1973 +-64, 1973 +-128, 1973 +-256, 1973 +-512, and 1973 +-2^10 are all composite.

Mathematica

cmpQ[p_]:=Module[{c=2^Range[0, (IntegerLength[p, 2]-1)]}, AllTrue[Flatten[p+{c, -c}], CompositeQ]]; Select[Prime[Range[5000]], cmpQ] (* Harvey P. Dale, Jun 04 2023 *)

Prog

(PARI)f(p)={v=binary(p); k=#v; for(i=0, k-1, if(isprime(p+2^i)||isprime(p-2^i), return(0))); return(1)}; forprime(p=2, 43759, if(f(p), print1(p, ", "))) \\ Washington Bomfim, Jan 18 2011

Crossrefs

Cf. A065092.

Subsequence of A255967.

Sequence in context: A183692 A206218 A255967 * A251816 A108386 A135844

Adjacent sequences: A153349 A153350 A153351 * A153353 A153354 A153355

Keyword

nonn,base

Author

Charles R Greathouse IV, Dec 24 2008

Extensions

Edited by Washington Bomfim, Jan 18 2011

Status

approved