A065111 -id:A065111 - cp's OEIS frontend

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

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

cp's OEIS Frontend

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