A065092 -id:A065092 - cp's OEIS frontend

A137985 Complementing any single bit in the binary representation of these primes does not produce a prime number.

127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443, 491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193, 1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777, 1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999

Offset: 1

T. D. Noe, Feb 26 2008

If 2^m is the highest power of 2 in the binary representation of the prime p, there is no requirement that p+2^(m+1) be composite. Sequence A065092 imposes this extra requirement. The prime 223 is the first number in this sequence that is not in A065092.
Mentioned Feb 25 2008 by Terence Tao in his blog http://terrytao.wordpress.com. Tao proves that there are an infinite number of these primes in every fixed base.
Digitally delicate primes in base 2. - Marc Morgenegg, Apr 21 2021

			The numbers produced by complementing each of the 8 bits of 223 are 95, 159, 255, 207, 215, 219, 221 and 222, which are all composite.

T. D. Noe, 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. Comp. 29 (1975), 79-81.
Warren D. Smith et al., Primes such that every bit matters?, Yahoo group "primenumbers", April 2013.
Warren D. Smith and others, Primes such that every bit matters?, digest of 14 messages in primenumbers Yahoo group, Apr 3 - Apr 9, 2013. [Cached copy]
Terence Tao, A remark on primality testing and decimal expansions, arXiv:0802.3361 [math.NT], 2008-2010; Journal of the Australian Mathematical Society 91:3 (2011), pp. 405-413.
Eric Weisstein, Weakly Prime. From MathWorld - A Wolfram Web Resource.
Wikipedia, Delicate prime

Cf. A050249 (analogous base 10 sequence), A186995 (weak primes in base n).

A065092 is a very similar sequence.

q:= p-> isprime(p) and not ormap(i->isprime(Bits[Xor](p, 2^i)), [$0..ilog2(p)]):
select(q, [$2..5000])[];  # Alois P. Heinz, Jul 28 2025

t={}; k=1; While[Length[t]<100, k++; p=Prime[k]; d=IntegerDigits[p,2]; n=Length[d]; i=0; While[iT. D. Noe *)
isWPbase2[z_] := NestWhile[#*2 &, 2, (# < z && ! PrimeQ@BitXor[z, #] &)] > z; Select[Prime /@ Range[3, PrimePi[10^6]], isWPbase2@# &] (* Terentyev Oleg, Jul 17 2011 *)
Select[Prime[Range[500]], NoneTrue[BitXor[#, 2^Range[0, BitLength[#] - 1]], PrimeQ] &] (* Paolo Xausa, Apr 23 2025 *)

f(p)={pow2=1;v=binary(p);L=#v;
forstep(k=L,1,-1,if(v[k],p-=pow2;if(isprime(p),return(0),p+=pow2),p+=pow2;if(isprime(p),return(0),p-=pow2)); pow2*=2);return(1)}; forprime(p=2,2879,if(f(p), print1(p,", "))) \\ Washington Bomfim, Jan 18 2011

is_A137985(n)=!for(k=1,n,isprime(bitxor(n,k)) && return;k+=k-1) && isprime(n) \\ Note: A bug in early versions of PARI 2.6 (execute "for(i=0,1,i>3 && error(buggy);i=9)" to check) makes that this is is_A065092 rather than is_A137985 as expected. For these versions, replace the upper limit n with n\2. \\ M. F. Hasler, Apr 05 2013

from sympy import isprime, primerange
def ok(p): # p assumed prime
  return not any(isprime((1<Michael S. Branicky, Feb 16 2021

Definition clarified by Chai Wah Wu, Jan 03 2019

Name edited by Paolo Xausa, Apr 24 2025

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

Original entry on oeis.org

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

Charles R Greathouse IV, Dec 24 2008

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.

			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.

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)

Cf. A065092.

Subsequence of A255967.

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

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

Edited by Washington Bomfim, Jan 18 2011

A065111 Dead-end primes in "The Prime Number Maze" reachable from 2.

Original entry on oeis.org

73, 89, 127, 349, 733, 773, 787, 1201, 1453, 1553, 1597, 1657, 1753, 1759, 1777, 1783, 1811, 1889, 1913

Offset: 1

William Paulsen (wpaulsen(AT)csm.astate.edu), Nov 12 2001

Is it possible that this sequence is an incorrect version of A065092? - Paul V. McKinney, May 20 2022
No. This sequence is a list of values for which reaching a Mersenne prime according to the rules of the maze is impossible. For 73 the only available move is to swap to 89, and vice versa (although there are other ways of reaching them, for example 601 can transition to 89). While 127 is already a Mersenne prime, it is not possible to reach another Mersenne prime starting from 127. In addition, to be included in this sequence, the value must be reachable starting from 2 (cf. A365001 for removal of this restriction). However, I'm not convinced that the current terms are complete. For example, should 173 be in this sequence? - Sean A. Irvine, Aug 15 2023
173 is of incorrect parity and therefore not reachable starting from 2. - Paul V. McKinney, Sep 21 2023

William Paulsen, The Prime Maze
William Paulsen, Are some rooms totally isolated?
William Paulsen, The Prime Maze, Fib. Quart., 40 (2002), 272-279.
Carlos Rivera, Problem 25. The William Paulsen's Prime Numbers Maze, The Prime Puzzles & Problems Connection.

Cf. A365001.

Corrected by T. D. Noe, Nov 14 2006

Title clarified by Sean A. Irvine, Aug 15 2023

A320102 Primes where changing any single bit in the binary representation never results in a smaller prime.

Original entry on oeis.org

2, 5, 17, 41, 73, 97, 127, 137, 149, 173, 191, 193, 223, 233, 239, 251, 257, 277, 281, 307, 331, 337, 349, 373, 389, 401, 431, 443, 491, 509, 521, 547, 557, 569, 577, 599, 617, 641, 653, 683, 701, 719, 733, 757, 761, 787, 809, 821, 839, 853, 877, 881, 907, 919, 977, 997, 1019, 1033, 1087, 1093, 1153

Offset: 1

Paul V. McKinney, Oct 06 2018

Rooms in Paulsen's prime number maze that are not connected to any room with a lesser room number.
"The prime number maze is a maze of prime numbers where two primes are connected if and only if their base 2 representations differ in just one bit." - William Paulsen (A065123).
If k is prime and the bit 2^m in k is 0 then 2^m+k is not in the sequence.
If k is in the sequence then 2^m+k is not where the bit 2^m in k is 0. - David A. Corneth, Oct 09 2018

			7 is not in the sequence because there is a way to change only one single bit of its binary representation that results in a prime smaller than 7 {1(1)1,(1)11} {5,3}.
41 is in the sequence because changing any single bit of its binary representation binary representation never results in a smaller prime {10100(1),10(1)001,(1)01001} {40,25,9}.

Michael S. Branicky, Table of n, a(n) for n = 1..10000
Paul V. McKinney, Fortran Program.

Cf. A019434, A137985, A065092, A065111, A065123.

FORTRAN
```
See "Links" for program.
```

q[p_] := PrimeQ[p] && AllTrue[2^(-1 + Position[Reverse @ IntegerDigits[p, 2], 1] // Flatten), !PrimeQ[p - #] &]; Select[Range[1000], q] (* Amiram Eldar, Jan 13 2022 *)

is(n) = if(!isprime(n), return(0)); b = binary(n); for(i=1, #b, if(b[i]==1, if(isprime(n-2^(#b-i)), return(0)))); 1 \\ David A. Corneth, Oct 09 2018

from sympy import isprime
def ok(n):
    if not isprime(n): return False
    onelocs = (i for i, bi in enumerate(bin(n)[2:][::-1]) if bi == '1')
    return not any(isprime(n-2**k) for k in onelocs)
print([k for k in range(1154) if ok(k)]) # Michael S. Branicky, Jan 10 2022

A365001 Primes from which it is not possible to reach a (different) Mersenne prime by toggling a single bit per step while still remaining prime at every step.

Original entry on oeis.org

73, 89, 127, 173, 191, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443, 491, 557, 653, 683, 701, 733, 761, 769, 773, 787, 853, 907, 911, 971, 1019, 1093, 1109, 1117, 1193, 1201, 1237, 1297, 1301, 1303, 1361, 1367, 1373, 1381, 1399, 1429, 1453, 1489, 1493

Offset: 1

Sean A. Irvine, Aug 15 2023

These are "locations" in The Prime Number Maze from which it is not possible to reach a (different) Mersenne prime by successively toggling single bits (see Paulsen for exact rules). This differs from A065111 in that it contains locations, such as 2131099, which are not reachable from 2.

			For 73 the only available move is to swap to 89, and vice versa (although there are other ways of reaching them, for example 601 can transition to 89). While 127 is already a Mersenne prime, it is not possible to reach another Mersenne prime starting from 127.

Sean A. Irvine, Java program (github)
W. Paulsen, The Prime Maze
W. Paulsen, Are some rooms totally isolated?
W. Paulsen, The Prime Maze, Fib. Quart., 40 (2002), 272-279.
Carlos Rivera, Problem 25. The William Paulsen's Prime Numbers Maze, The Prime Puzzles & Problems Connection.

Cf. A065111 (reachable from 2), A065092 (singularly dead end primes).

Missing terms inserted by Andrew Howroyd and name clarified by Sean A. Irvine, Sep 21 2023

A385245 Primes that are no longer prime if in their binary representation any single bit is flipped but stay prime if a 1 bit is prepended.

Original entry on oeis.org

223, 257, 509, 787, 853, 877, 1259, 1451, 1973, 2917, 3511, 5099, 6287, 6521, 7841, 8171, 8923, 9319, 10567, 11353, 12517, 12637, 12763, 13687, 14107, 14629, 15217, 15607, 16943, 17519, 18089, 18593, 18743, 19139, 20183, 20393, 20639, 21701, 22943, 26591, 26891

Offset: 1

Alois P. Heinz, Jul 28 2025

			257 = 100000001_2 and 769 = 1100000001_2 are primes and 256, 259, 261, 265, 273, 289, 321, 385, 1 are not prime. So 257 is a term.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Set difference of A137985 and A065092.

Cf. A000040, A002808.

q:= p-> (m-> andmap(isprime, [p, 2^(m+1)+p]) and not ormap
        (i->isprime(Bits[Xor](p, 2^i)), [$0..m]))(ilog2(p)):
select(q, [$2..27000])[];

Select[Prime[Range[3000]], PrimeQ[2^BitLength[#] + #] && NoneTrue[BitXor[#, 2^Range[0, BitLength[#] - 1]], PrimeQ] &] (* Paolo Xausa, Aug 05 2025 *)

{ A137985 } minus { A065092 }.

cp's OEIS Frontend

A137985 Complementing any single bit in the binary representation of these primes does not produce a prime number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A065111 Dead-end primes in "The Prime Number Maze" reachable from 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A320102 Primes where changing any single bit in the binary representation never results in a smaller prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

FORTRAN

Mathematica

PARI

Python

A365001 Primes from which it is not possible to reach a (different) Mersenne prime by toggling a single bit per step while still remaining prime at every step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A385245 Primes that are no longer prime if in their binary representation any single bit is flipped but stay prime if a 1 bit is prepended.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula