A342244 - OEIS

%I #31 May 22 2024 17:27:30

%S 2,3,5,7,13,17,41,73,89,97,137,193,257,281,313,409,449,521,569,577,

%T 617,641,673,761,769,929,953,1033,1049,1153,1249,1289,1409,1601,1657,

%U 1697,1721,1801,1913,2081,2113,2153,2297,2441,2593,2713,3137,3257,3361,3449

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

%C 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).

%C Empirically, a(n) == 1 (mod 8) after starting at a(6)=17. - _Hugo Pfoertner_, Mar 06 2021

%C 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

%H Robert Israel, <a href="/A342244/b342244.txt">Table of n, a(n) for n = 1..10000</a>

%p CSP:= proc(n)  option remember; local g;

%p    g:= proc(k) local v; v:= n mod 2^k; isprime(floor(n/2^k)) and (isprime(v) or CSP(v)) end proc;

%p    ormap(g, [$2..ilog2(n)])

%p end proc:

%p CSP(0):= false:

%p remove(CSP, [seq(ithprime(i),i=1..1000)]); # _Robert Israel_, May 22 2024

%o (Python)

%o from sympy import isprime, primerange

%o def ok(p):

%o   b = bin(p)[2:]

%o   for i in range(2, len(b)-1):

%o     if isprime(int(b[:i], 2)):

%o       if isprime(int(b[i:], 2)) or not ok(int(b[i:], 2)): return False

%o   return True

%o def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]

%o print(aupto(3449)) # _Michael S. Branicky_, Mar 07 2021

%Y Cf. A090422.

%K nonn,base

%O 1,1

%A _Jeffrey Shallit_, Mar 07 2021