A342244 -id:A342244 - cp's OEIS frontend

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

Reinhard Zumkeller, Nov 30 2003

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

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

Cf. A090423, A000040, A004676, A007088.

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

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

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

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

A348358 Primes which are not the concatenation of smaller primes (in base 10 and allowing leading 0's).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 41, 43, 47, 59, 61, 67, 71, 79, 83, 89, 97, 101, 103, 107, 109, 127, 131, 139, 149, 151, 157, 163, 167, 179, 181, 191, 199, 239, 251, 263, 269, 281, 349, 401, 409, 419, 421, 431, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499

Offset: 1

M. Farrokhi D. G., Oct 14 2021

This is the sequence of numbers that are neither a product of smaller primes nor a concatenation of smaller primes (in base 10).
This sequence differs from A238647. The prime 227 is in A238647 but not in this sequence for it is the concatenation of primes 2, 2, 7 (in base 10).
Conjecture. If p > 7 is a prime, then there exists a base b such that p in base b is the concatenation of smaller primes in base b.

			The prime 127 is in the sequence because the only expressions of 127 as concatenation of smaller numbers are 1 U 2 U 7, 1 U 27, and 12 U 7 (in base 10) but 1 and 12 are not primes.
The prime 271 is not in the sequence because it is the concatenation of primes 2 and 71 (in base 10).
The prime 307 is not in the sequence because it is the concatenation of primes 3 and 07 (in base 10).

Cf. A141033, A141409, A238647, A342244, A348358.

Select[Prime@Range@100,Union[And@@@PrimeQ[FromDigits/@#&/@Union@Select[Flatten[Permutations/@Subsets[Most@Rest@Subsequences[d=IntegerDigits@#]],1],Flatten@#==d&]]]=={False}||Length@d==1&] (* Giorgos Kalogeropoulos, Oct 15 2021 *)

from sympy import isprime, primerange
def cond(n): # n is not a concatenation of smaller primes
    if n%10 in {4, 6, 8}: return True
    d = str(n)
    for i in range(1, len(d)):
        if isprime(int(d[:i])):
             if isprime(int(d[i:])) or not cond(int(d[i:])):
                 return False
    return True
def aupto(lim): return [p for p in primerange(2, lim+1) if cond(p)]
print(aupto(490)) # Michael S. Branicky, Oct 15 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

Extensions