A342244 Primes whose binary representation is not the concatenation of the binary representations of smaller primes (allowing leading 0's).

2, 3, 5, 7, 13, 17, 41, 73, 89, 97, 137, 193, 257, 281, 313, 409, 449, 521, 569, 577, 617, 641, 673, 761, 769, 929, 953, 1033, 1049, 1153, 1249, 1289, 1409, 1601, 1657, 1697, 1721, 1801, 1913, 2081, 2113, 2153, 2297, 2441, 2593, 2713, 3137, 3257, 3361, 3449

Offset

1,1

Comments

Similar to A090422, but allowing leading zeros in the representation of any prime. For example, 19 in base 2 is 10011, which can be written as (10)(011), and so does not appear in this sequence (but does appear in A090422).

Empirically, a(n) == 1 (mod 8) after starting at a(6)=17. - Hugo Pfoertner, Mar 06 2021

This observation follows from the fact that the regular expression (0*10+0*11+0*101+0*111+0*1011+0*1101)* corresponding to the first 6 primes has a complement that only includes 1, 01, some words that end in 0, and some words that end in 001. - Jeffrey Shallit, Mar 07 2021

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Maple

CSP:= proc(n)  option remember; local g;
   g:= proc(k) local v; v:= n mod 2^k; isprime(floor(n/2^k)) and (isprime(v) or CSP(v)) end proc;
   ormap(g, [$2..ilog2(n)])
end proc:
CSP(0):= false:
remove(CSP, [seq(ithprime(i), i=1..1000)]); # Robert Israel, May 22 2024

Prog

(Python)
from sympy import isprime, primerange
def ok(p):
  b = bin(p)[2:]
  for i in range(2, len(b)-1):
    if isprime(int(b[:i], 2)):
      if isprime(int(b[i:], 2)) or not ok(int(b[i:], 2)): return False
  return True
def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]
print(aupto(3449)) # Michael S. Branicky, Mar 07 2021

Crossrefs

Cf. A090422.

Sequence in context: A028865 A053435 A096478 * A076047 A245640 A365274

Adjacent sequences: A342241 A342242 A342243 * A342245 A342246 A342247

Keyword

nonn,base

Author

Jeffrey Shallit, Mar 07 2021

Status

approved