A090423 -id:A090423 - cp's OEIS frontend

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

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

A344371 a(n) = Sum_{k=1..n} (-1)^(n-k) gcd(k,n).

Original entry on oeis.org

1, 1, 3, 4, 5, 5, 7, 12, 9, 9, 11, 20, 13, 13, 15, 32, 17, 21, 19, 36, 21, 21, 23, 60, 25, 25, 27, 52, 29, 45, 31, 80, 33, 33, 35, 84, 37, 37, 39, 108, 41, 65, 43, 84, 45, 45, 47, 160, 49, 65, 51, 100, 53, 81, 55, 156, 57, 57, 59, 180, 61, 61, 63, 192, 65, 105

Offset: 1

Max Alekseyev, May 16 2021

Felix Fröhlich, Table of n, a(n) for n = 1..10000

Cf. A001620, A090423, A106475, A199084, A306016, A344372, A344373.

a(n) = sum(k=1, n, (-1)^(n-k)*gcd(k,n)); \\ Michel Marcus, May 16 2021

a(n) = abs(A199084(n)).
a(2n+1) = 2n+1.
a(2n) = A344372(n) = 2*n - A106475(n-1).
Sum_{k=1..n} a(k) ~ (n^2/Pi^2) * (log(n) + 2*gamma - 1/2 - 4*log(2)/3 + Pi^2/4 - zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). - Amiram Eldar, Mar 30 2024

More terms from Felix Fröhlich, May 19 2021

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

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

A191235 Primes p such that the binary representation of p is the concatenation of the binary representations of prime 2 and an odd prime.

Original entry on oeis.org

11, 23, 43, 83, 181, 353, 359, 383, 643, 661, 691, 709, 739, 751, 1301, 1307, 1361, 1373, 1433, 1481, 1487, 1511, 1523, 2617, 2647, 2689, 2707, 2731, 2749, 2767, 2791, 2857, 2887, 3001, 3019, 3061, 3067, 5147, 5189, 5297, 5309, 5333, 5387, 5393

Offset: 1

Juri-Stepan Gerasimov, May 27 2011

The odd primes arising in computing the sequence are 3, 7, 11, 19, 53, 97, 103, 127, 131, 149, 179, 197, 227, 239, ...

Primes whose binary representation equals the binary representation of some prime preceded by 10. - Klaus Brockhaus, May 29 2011

			11 is in the sequence because 11, 2, 3 in binary are resp. 1011, 10, 11.
83 is in the sequence because 83, 2, 19 in binary are resp. 1010011, 10, 10011.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A004676, A007088, A091932, A080165, A090423, A053644.

[ p: p in PrimesInInterval(3, 6100) | exists(q){ k: k in PrimesUpTo(p div 3) | Intseq(p, 2) eq Intseq(k, 2) cat [0, 1] } ]; // Klaus Brockhaus, May 29 2011

A053644(n)=my(k=1);while(k<=n,k<<=1);k>>1;
forprime(p=2,1e3,if(isprime(k=4*A053644(p)+p),print1(k", "))) \\ Charles R Greathouse IV, May 27 2011

a(4) corrected, a(15)-a(56) added by Charles R Greathouse IV, May 27 2011

A214754 Primes that can be written in binary representation as a concatenation of odd primes.

Original entry on oeis.org

23, 29, 31, 47, 59, 61, 71, 79, 109, 113, 127, 151, 157, 167, 179, 191, 223, 229, 233, 239, 241, 251, 271, 283, 317, 349, 359, 367, 373, 379, 383, 431, 433, 439, 457, 463, 467, 479, 487, 491, 499, 503, 509, 541, 563, 599, 607, 631, 701, 719, 727, 733, 743, 751, 757

Offset: 1

Alex Ratushnyak, Aug 03 2012

Subsequence of A090423.

			31 is 11111 in binary, 11 is 3 in decimal, 111 is 7, partition exists: 11_111, so 31 is in the sequence.

David Radcliffe, Table of n, a(n) for n = 1..10000

Cf. A090423.

# oddPrimes = [3, ... , 757]
def tryPartitioning(binString):  # First digit is not 0
    if binString=='10':
        return 0
    l = len(binString)
    for t in range(2, l-1):
        substr1 = binString[:t]
        if (int('0b'+substr1,2) in oddPrimes) or (t>=4 and tryPartitioning(substr1)):
            substr2 = binString[t:]
            if substr2[0]!='0':
                if (int('0b'+substr2,2) in oddPrimes) or (l-t>=4 and tryPartitioning(substr2)):
                    return 1
    return 0
for p in oddPrimes:
    if tryPartitioning(bin(p)[2:]):
        print(p, end=', ')

A232085 Primes that can be written in binary representation as concatenation of two primes. That is, primes representable as p * 2^L + q, where p and q are primes, and L is the length of binary representation of q: L = A070939(q).

Original entry on oeis.org

11, 23, 29, 31, 43, 47, 59, 61, 71, 79, 83, 109, 113, 127, 151, 157, 167, 179, 181, 191, 229, 233, 239, 241, 251, 271, 283, 317, 349, 353, 359, 367, 373, 379, 383, 431, 433, 439, 457, 463, 467, 479, 487, 491, 509, 541, 563, 599, 607, 631, 643, 661, 691, 701, 709, 719

Offset: 1

Alex Ratushnyak, Nov 17 2013

A subsequence of A090423.

Cf. A000040, A070939, A090423.

A257371 Number of states in minimal DFA for P_n^*, where P_n is the set of base-2 representations of the first n prime numbers.

Original entry on oeis.org

3, 3, 5, 5, 5, 7, 8, 8, 8, 8, 8, 9, 12, 12, 12, 15, 15, 15, 17, 17, 18, 18, 18, 19, 29, 29, 31, 31, 31, 31, 31, 33, 34, 34, 35, 35, 35, 37, 37, 37, 37, 37, 37, 38, 41, 40, 41, 41, 49, 49, 49, 49, 49, 49, 51, 52, 53, 53, 55, 59, 59, 59, 62, 62, 63, 63, 65, 65

Offset: 1

Jeffrey Shallit, Apr 21 2015

nonn

Here by "DFA" we mean "deterministic finite automaton", and by P_n^* we mean the set of all binary strings that can be formed as the concatenation of 0 or more of the base-2 representations of the first n primes. The DFA must be "complete" (there must be a transition for each state and symbol) and hence includes any "dead state".

P_n^* is identical to P_{n-1}^* when prime(n) in binary is the concatenation of smaller primes, since it adds nothing to the pattern. So a(n) = a(n-1) when n in A090423, though various other a(n) = a(m) occur too when different state machines happen to have the same state count. - Kevin Ryde, Dec 26 2020

			From _Kevin Ryde_, Dec 26 2020: (Start)
For n=3, primes 2,3,5 in binary are 10,11,101 and the regular expression is P_3^* = (10|11|101)*.  State machine manipulations, or some thought about these bits, gives the following minimum DFA comprising a(3) = 5 states.  States A,C,D are accepting.  States B and dead are non-accepting.  Dead is reached when some initial part of the input string shows the whole will not match, no matter what follows.
  start
  +===+  1   +---+  0   +===+  1   +===+
  | A | ---> | B | ---> | C | ---> | D |
  +===+ <--- +---+      +===+ <--- +===+
    |0    1               |0    0   ^ |1
    |       +------+      |         +-+
    +-----> | dead | <----+
            +------+
              ^ | 0,1
              +-+
(End)

Kevin Ryde, Table of n, a(n) for n = 1..10000
Kevin Ryde, Perl program running Foma (or others) to make a b-file

Cf. A004676, A090423, A257291.

a(26)-a(68) from Kevin Ryde, Dec 27 2020

cp's OEIS Frontend

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

A344371 a(n) = Sum_{k=1..n} (-1)^(n-k) gcd(k,n).

Views

Author

Keywords

Links

Crossrefs

Programs

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

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

A191235 Primes p such that the binary representation of p is the concatenation of the binary representations of prime 2 and an odd prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

PARI

Extensions

A214754 Primes that can be written in binary representation as a concatenation of odd primes.

Views

Author