cp's OEIS Frontend

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

%I A342244 #31 May 22 2024 17:27:30
%S A342244 2,3,5,7,13,17,41,73,89,97,137,193,257,281,313,409,449,521,569,577,
%T A342244 617,641,673,761,769,929,953,1033,1049,1153,1249,1289,1409,1601,1657,
%U A342244 1697,1721,1801,1913,2081,2113,2153,2297,2441,2593,2713,3137,3257,3361,3449
%N A342244 Primes whose binary representation is not the concatenation of the binary representations of smaller primes (allowing leading 0's).
%C A342244 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 A342244 Empirically, a(n) == 1 (mod 8) after starting at a(6)=17. - _Hugo Pfoertner_, Mar 06 2021
%C A342244 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 A342244 Robert Israel, <a href="/A342244/b342244.txt">Table of n, a(n) for n = 1..10000</a>
%p A342244 CSP:= proc(n)  option remember; local g;
%p A342244    g:= proc(k) local v; v:= n mod 2^k; isprime(floor(n/2^k)) and (isprime(v) or CSP(v)) end proc;
%p A342244    ormap(g, [$2..ilog2(n)])
%p A342244 end proc:
%p A342244 CSP(0):= false:
%p A342244 remove(CSP, [seq(ithprime(i),i=1..1000)]); # _Robert Israel_, May 22 2024
%o A342244 (Python)
%o A342244 from sympy import isprime, primerange
%o A342244 def ok(p):
%o A342244   b = bin(p)[2:]
%o A342244   for i in range(2, len(b)-1):
%o A342244     if isprime(int(b[:i], 2)):
%o A342244       if isprime(int(b[i:], 2)) or not ok(int(b[i:], 2)): return False
%o A342244   return True
%o A342244 def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]
%o A342244 print(aupto(3449)) # _Michael S. Branicky_, Mar 07 2021
%Y A342244 Cf. A090422.
%K A342244 nonn,base
%O A342244 1,1
%A A342244 _Jeffrey Shallit_, Mar 07 2021