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

Author

Jeffrey Shallit, Mar 07 2021

Keywords

• nonn
• base

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

Crossrefs

Cf. A090422.

Programs

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

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