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

2, 3, 5, 7, 13, 17, 19, 37, 41, 53, 67, 73, 89, 97, 101, 103, 107, 131, 137, 139, 149, 163, 193, 197, 199, 211, 227, 257, 263, 269, 277, 281, 293, 307, 311, 313, 331, 389, 397, 401, 409, 419, 421, 443, 449, 461, 521, 523, 547, 557, 569, 571, 577, 587, 593

Offset: 1

Author

Reinhard Zumkeller, Nov 30 2003

Keywords

• nonn
• base

Comments

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

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A090423, A000040, A004676, A007088.

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

Programs

Haskell

a090422 n = a090422_list !! (n-1)
a090422_list = filter ((== 1) . a090418 . fromInteger) a000040_list
-- Reinhard Zumkeller, Aug 07 2012

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)) and b[i] != '0':
      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(593)) # Michael S. Branicky, Mar 07 2021

Extensions

Based on corrections in A090418, data recomputed by Reinhard Zumkeller, Aug 07 2012