cp's OEIS Frontend

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

%I A090422 #19 Mar 07 2021 14:40:43
%S A090422 2,3,5,7,13,17,19,37,41,53,67,73,89,97,101,103,107,131,137,139,149,
%T A090422 163,193,197,199,211,227,257,263,269,277,281,293,307,311,313,331,389,
%U A090422 397,401,409,419,421,443,449,461,521,523,547,557,569,571,577,587,593
%N A090422 Primes that cannot be written in binary representation as concatenation of other primes.
%C A090422 A090418(a(n)) = 1; subsequence of A090421.
%C A090422 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 A090422 Reinhard Zumkeller, <a href="/A090422/b090422.txt">Table of n, a(n) for n = 1..10000</a>
%o A090422 (Haskell)
%o A090422 a090422 n = a090422_list !! (n-1)
%o A090422 a090422_list = filter ((== 1) . a090418 . fromInteger) a000040_list
%o A090422 -- _Reinhard Zumkeller_, Aug 07 2012
%o A090422 (Python)
%o A090422 from sympy import isprime, primerange
%o A090422 def ok(p):
%o A090422   b = bin(p)[2:]
%o A090422   for i in range(2, len(b)-1):
%o A090422     if isprime(int(b[:i], 2)) and b[i] != '0':
%o A090422       if isprime(int(b[i:], 2)) or not ok(int(b[i:], 2)): return False
%o A090422   return True
%o A090422 def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]
%o A090422 print(aupto(593)) # _Michael S. Branicky_, Mar 07 2021
%Y A090422 Cf. A090423, A000040, A004676, A007088.
%Y A090422 A342244 handles the case where the primes are allowed to have leading zeros.
%K A090422 nonn,base
%O A090422 1,1
%A A090422 _Reinhard Zumkeller_, Nov 30 2003
%E A090422 Based on corrections in A090418, data recomputed by _Reinhard Zumkeller_, Aug 07 2012