login
Primes that cannot be written in binary representation as concatenation of other primes.
5

%I #19 Mar 07 2021 14:40:43

%S 2,3,5,7,13,17,19,37,41,53,67,73,89,97,101,103,107,131,137,139,149,

%T 163,193,197,199,211,227,257,263,269,277,281,293,307,311,313,331,389,

%U 397,401,409,419,421,443,449,461,521,523,547,557,569,571,577,587,593

%N Primes that cannot be written in binary representation as concatenation of other primes.

%C A090418(a(n)) = 1; subsequence of A090421.

%C This sequence is indeed infinite, as we need infinitely many terms to cover the primes with arbitrarily large runs of 0's in their base-2 representation. - _Jeffrey Shallit_, Mar 07 2021

%H Reinhard Zumkeller, <a href="/A090422/b090422.txt">Table of n, a(n) for n = 1..10000</a>

%o (Haskell)

%o a090422 n = a090422_list !! (n-1)

%o a090422_list = filter ((== 1) . a090418 . fromInteger) a000040_list

%o -- _Reinhard Zumkeller_, Aug 07 2012

%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)) and b[i] != '0':

%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(593)) # _Michael S. Branicky_, Mar 07 2021

%Y Cf. A090423, A000040, A004676, A007088.

%Y A342244 handles the case where the primes are allowed to have leading zeros.

%K nonn,base

%O 1,1

%A _Reinhard Zumkeller_, Nov 30 2003

%E Based on corrections in A090418, data recomputed by _Reinhard Zumkeller_, Aug 07 2012