OFFSET
1,1
COMMENTS
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
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..10000
Paul V. McKinney, Fortran Program.
EXAMPLE
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}.
MATHEMATICA
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 *)
PROG
(PARI) 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
(FORTRAN) See "Links" for program.
(Python)
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
CROSSREFS
KEYWORD
base,nonn
AUTHOR
Paul V. McKinney, Oct 06 2018
STATUS
approved