A090421 -id:A090421 - 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

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

Original entry on oeis.org

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

A090419 Numbers that cannot be written in binary representation as concatenation of primes.

Original entry on oeis.org

1, 4, 6, 8, 9, 12, 16, 18, 20, 24, 25, 26, 27, 28, 32, 33, 34, 35, 36, 38, 39, 40, 44, 48, 49, 50, 51, 52, 56, 57, 60, 64, 65, 66, 68, 69, 72, 74, 75, 76, 77, 80, 82, 84, 88, 92, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 112, 114, 116, 120, 121, 124

Offset: 1

Reinhard Zumkeller, Nov 30 2003

A090418(a(n)) = 0; complement of A090421.

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

Cf. A004676, A007088.

a090419 n = a090419_list !! (n-1)
a090419_list = filter ((== 0) . a090418) [1..]
-- Reinhard Zumkeller, Aug 06 2012

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

A090420 Numbers having a unique representation as concatenation of primes in binary.

Original entry on oeis.org

2, 3, 5, 7, 10, 13, 14, 15, 17, 19, 21, 22, 30, 37, 41, 42, 53, 54, 55, 58, 62, 67, 70, 73, 78, 81, 85, 86, 89, 90, 97, 101, 103, 107, 111, 115, 117, 122, 131, 137, 139, 141, 143, 149, 150, 159, 163, 165, 166, 169, 170, 177, 193, 197, 199, 211, 214, 215, 218

Offset: 1

Reinhard Zumkeller, Nov 30 2003

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

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

Cf. A004676, A007088.

Cf. A090423 (subsequence).

a090420 n = a090420_list !! (n-1)
a090420_list = filter ((== 1) . a090418) [1..]
-- Reinhard Zumkeller, Aug 07 2012

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

A257318 Numbers n whose binary expansion can be written as the concatenation of the binary expansion of prime numbers in at least two different ways (not allowing leading zeros).

Original entry on oeis.org

11, 23, 29, 31, 43, 45, 46, 47, 59, 61, 63, 71, 79, 83, 87, 91, 93, 94, 95, 109, 113, 118, 119, 123, 125, 126, 127, 151, 157, 167, 171, 173, 174, 175, 179, 181, 182, 183, 186, 187, 189, 190, 191, 219, 223, 229, 233, 235, 237, 238, 239, 241, 245, 246, 247, 251, 253, 254, 255, 271, 283, 286, 287

Offset: 1

Jeffrey Shallit, Apr 20 2015

Numbers such that A090418(n)>1. A090423 is a subsequence. - M. F. Hasler, Apr 21 2015

			The first term is 11, as 11 in base 2 is 1011, which can be written either as (1011) or (10)(11).

M. F. Hasler, Table of n, a(n) for n = 1..1000

Cf. A090421.

is_A257318(n)={A090418(n)>1} \\ M. F. Hasler, Apr 21 2015

A256872 Numbers whose binary expansion is the concatenation of the binary expansion of two prime numbers in at least two ways.

Original entry on oeis.org

23, 31, 45, 47, 61, 93, 95, 119, 125, 127, 175, 187, 189, 191, 239, 247, 253, 255, 335, 357, 359, 363, 369, 379, 381, 383, 431, 439, 455, 477, 485, 491, 493, 495, 507, 509, 511, 573, 575, 631, 637, 639, 669, 671

Offset: 1

M. F. Hasler, Apr 21 2015

A simplified variant (and subsequence) of A257318 (and A090421) where the concatenation of any number of primes is considered.
The subsequence of numbers which are concatenation of 2 primes in at least 3 ways is (93, 95, 189, 191, 239, 253, 335, 381, 383, 669, ...).
All terms are odd. Indeed, if an even number n > 2 is concatenation of two primes (in binary), then it is of the form 'n' = 'floor(n/4)''2' (where 'x' is x in binary), and there is no other possible decomposition.

			23 = 10111[2] = (10[2])(111[2]) = (101[2])(11[2]) which is (2)(7) resp. (5)(3).

Cf. A090418, A090421, A090423, A257318.

is(n,c=2)={for(i=2,#binary(n)-2,bittest(n,i-1)&&isprime(n>>i)&&isprime(n%2^i)&&!c--&&return(1))}

A090418(a(n)) >= 2. (Necessary but not sufficient condition. This actually characterizes elements of A257318. For example, all terms of A090423 satisfy this but many of them are not terms of this sequence.)

A298746 Numbers n whose base-2 representation can be written as the concatenation of the base-2 representations of a list of prime numbers, allowing leading zeros.

Original entry on oeis.org

2, 3, 5, 7, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 26, 27, 29, 30, 31, 34, 35, 37, 39, 41, 42, 43, 45, 46, 47, 50, 51, 53, 54, 55, 58, 59, 61, 62, 63, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 81, 82, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 98, 99, 101, 103, 106, 107, 109, 110, 111, 113, 114, 115, 117, 118

Offset: 1

Jeffrey Shallit, Jan 25 2018

Has positive density in the positive integers, which can be proved by considering only those numbers obtained using the primes 2 and 3.

			For example, 26 is such a number because 26 in base 2 is 11010, which can be written as the concatenation (11)(010).

Cf. A090421, which does not allow leading zeros.

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

Extensions

A090419 Numbers that cannot be written in binary representation as concatenation of primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Extensions

A090420 Numbers having a unique representation as concatenation of primes in binary.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Extensions

A257318 Numbers n whose binary expansion can be written as the concatenation of the binary expansion of prime numbers in at least two different ways (not allowing leading zeros).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A256872 Numbers whose binary expansion is the concatenation of the binary expansion of two prime numbers in at least two ways.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A298746 Numbers n whose base-2 representation can be written as the concatenation of the base-2 representations of a list of prime numbers, allowing leading zeros.

Views