A090422 -id:A090422 - cp's OEIS frontend

A090423 Primes that can be written in binary representation as concatenation of other primes.

11, 23, 29, 31, 43, 47, 59, 61, 71, 79, 83, 109, 113, 127, 151, 157, 167, 173, 179, 181, 191, 223, 229, 233, 239, 241, 251, 271, 283, 317, 337, 347, 349, 353, 359, 367, 373, 379, 383, 431, 433, 439, 457, 463, 467, 479, 487, 491, 499, 503, 509, 541, 563, 599, 607

Offset: 1

Reinhard Zumkeller, Nov 30 2003

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

			337 is 101010001 in binary,
10 is 2,
10 is 2,
10001 is 17, partition is 10_10_10001, so 337 is in the sequence.

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

Cf. A090422, A000040, A004676, A007088.

a090423 n = a090423_list !! (n-1)
a090423_list = filter ((> 1 ) . a090418 . fromInteger) a000040_list
-- Reinhard Zumkeller, Aug 06 2012

is_A090423(n)={isprime(n)&&for(i=2, #binary(n)-2, bittest(n, i-1)&&isprime(n%2^i)&&is_A090421(n>>i)&&return(1))} \\ M. F. Hasler, Apr 21 2015

# Primes = [2,...,607]
from sympy import sieve
primes = list(sieve.primerange(1, 608))
def tryPartioning(binString):   # First digit is not 0
    l = len(binString)
    for t in range(2, l-1):
        substr1 = binString[:t]
        if (int('0b'+substr1,2) in primes) or (t>=4 and tryPartioning(substr1)):
            substr2 = binString[t:]
            if substr2[0]!='0':
                if (int('0b'+substr2,2) in primes) or (l-t>=4 and tryPartioning(substr2)):
                    return 1
    return 0
for p in primes:
    if tryPartioning(bin(p)[2:]):
        print(p, end=',')

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 ok(int(b[i:], 2)): return True
  return False
def aupto(lim): return [p for p in primerange(2, lim+1) if ok(p)]
print(aupto(607)) # Michael S. Branicky, May 16 2021

Corrected by Alex Ratushnyak, Aug 03 2012

A090418 Number of ways to write n in binary representation as a concatenation of primes.

Original entry on oeis.org

0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 2, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 3, 0, 0, 0, 0, 0, 2, 1, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 3, 0, 2, 2, 4, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 3, 0, 3, 1, 2, 0, 0, 0, 1, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 2, 0, 1, 1

Offset: 0

Reinhard Zumkeller, Nov 30 2003

			n=23 -> '10111': '10"111'==2"7, '101"11'==5"3 and '10111'==23, therefore a(23)=3.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (corrected by _Georg Fischer_, Jan 20 2019)

Cf. A004676, A007088.
Cf. A191232, A000040.
Cf. A090421, A090423, A257318.

import Data.List (stripPrefix, unfoldr)
import Data.Maybe (fromJust)
a090418 n = a090418_list !! (n-1)
a090418_list = 0 : f 2 where
   f x = (sum $ map g bpss) : f (x + 1) where
     g ps | suffix == Nothing = 0
          | suffix' == []     = 1
          | last suffix' == 0 = 0
          | otherwise         = a090418 $ fromBits suffix'
          where suffix' = fromJust suffix
                suffix = stripPrefix ps $ toBits x
     bpss = take (fromInteger $ a000720 x) $
                  map (toBits . fromInteger) a000040_list
   toBits = unfoldr
            (\u -> if u == 0 then Nothing else Just (mod u 2, div u 2))
   fromBits = foldr (\b v -> 2 * v + b) 0
-- Reinhard Zumkeller, Aug 06 2012

A090418(n)={ while( n>9 && !bittest(n,0), bittest(n,1)||return; n>>=2); n<10 && return(isprime(n)); sum(k=2, #binary(n)-2, if(bittest(n, k-1)&&isprime(n%2^k), A090418(n>>k)),isprime(n))} \\ M. F. Hasler, Apr 21 2015

a(A090419(n))=0; a(A090420(n))=1; a(A090421(n))>0;
a(A090422(n))=1; a(A090423(n))>1;
a(A090424(n)) = n and a(m) <> n for m < A090424(n).
a(n) = 0 if a = 0 (mod 4); a(n) = a(floor(n/4)) if a = 2 (mod 4). - M. F. Hasler, Apr 21 2015

Thanks to Alex Ratushnyak, who found an error in A090423, which was the consequence of errors in this sequence; the program was rewritten and data was recomputed by Reinhard Zumkeller, Aug 06 2012

Data in b-file double-checked with independent PARI code by M. F. Hasler, Apr 21 2015

A090421 Numbers that can be written in binary representation as concatenation of primes.

Original entry on oeis.org

2, 3, 5, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 29, 30, 31, 37, 41, 42, 43, 45, 46, 47, 53, 54, 55, 58, 59, 61, 62, 63, 67, 70, 71, 73, 78, 79, 81, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 101, 103, 107, 109, 111, 113, 115, 117, 118, 119, 122, 123

Offset: 1

Reinhard Zumkeller, Nov 30 2003

A090418(a(n)) > 0; complement of A090419.

Terms in the sequence cannot end in 00, 0010, 001010, etc., and thus a(n) > 3n/2 + O(log n). - Charles R Greathouse IV, Apr 21 2015

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

Cf. A004676, A007088, A090422.

Cf. A000040, A090420, and A090423 are subsequences.

a090421 n = a090421_list !! (n-1)
a090421_list = filter ((> 0) . a090418) [1..]
-- Reinhard Zumkeller, Aug 06 2012

is_A090421(n)={isprime(n) || if(bittest(n,0),for(k=2,#binary(n)-2,bittest(n,k-1) && isprime(n%2^k) && is_A090421(n>>k) && return(1)), bittest(n,1) && is_A090421(n>>2))} \\ Charles R Greathouse IV and M. F. Hasler, Apr 21 2015

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

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

Original entry on oeis.org

2, 3, 5, 7, 13, 17, 41, 73, 89, 97, 137, 193, 257, 281, 313, 409, 449, 521, 569, 577, 617, 641, 673, 761, 769, 929, 953, 1033, 1049, 1153, 1249, 1289, 1409, 1601, 1657, 1697, 1721, 1801, 1913, 2081, 2113, 2153, 2297, 2441, 2593, 2713, 3137, 3257, 3361, 3449

Offset: 1

Jeffrey Shallit, Mar 07 2021

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).
Empirically, a(n) == 1 (mod 8) after starting at a(6)=17. - Hugo Pfoertner, Mar 06 2021
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

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A090422.

CSP:= proc(n)  option remember; local g;
   g:= proc(k) local v; v:= n mod 2^k; isprime(floor(n/2^k)) and (isprime(v) or CSP(v)) end proc;
   ormap(g, [$2..ilog2(n)])
end proc:
CSP(0):= false:
remove(CSP, [seq(ithprime(i),i=1..1000)]); # Robert Israel, May 22 2024

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)):
      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(3449)) # Michael S. Branicky, Mar 07 2021

cp's OEIS Frontend

A090423 Primes that can be written in binary representation as concatenation of other primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Python

Python

Extensions

A090418 Number of ways to write n in binary representation as a concatenation of primes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

PARI

Formula

Extensions

A090421 Numbers that can be written in binary representation as concatenation of primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python