login
A342244
Primes whose binary representation is not the concatenation of the binary representations of smaller primes (allowing leading 0's).
3
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
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
KEYWORD
nonn,base
AUTHOR
Jeffrey Shallit, Mar 07 2021
STATUS
approved