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

Author

Charles R Greathouse IV, Dec 24 2008

Keywords

• nonn
• base

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.

Examples

			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.
		

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)

Crossrefs

Cf. A065092.

Subsequence of A255967.

Programs

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

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

Extensions

Edited by Washington Bomfim, Jan 18 2011