A078826 -id:A078826 - cp's OEIS frontend

A071338 Duplicate of A078826.

0, 1, 1, 1, 2, 2, 2, 1, 1, 2, 4, 2, 4, 3, 2, 1, 2, 1, 3, 2, 2, 4, 6, 2, 2, 4, 5, 3, 6, 3, 3, 1, 1, 2, 3

Offset: 1

dead

A078822 Number of distinct binary numbers contained as substrings in the binary representation of n.

1, 1, 3, 2, 4, 4, 5, 3, 5, 5, 5, 6, 7, 7, 7, 4, 6, 6, 6, 7, 7, 6, 8, 8, 9, 9, 9, 9, 10, 10, 9, 5, 7, 7, 7, 8, 7, 8, 9, 9, 9, 9, 7, 9, 11, 10, 11, 10, 11, 11, 11, 11, 12, 11, 11, 12, 13, 13, 13, 13, 13, 13, 11, 6, 8, 8, 8, 9, 8, 9, 10, 10, 9, 8, 10, 11, 11, 12, 12, 11, 11, 11, 11, 12, 10, 8

Offset: 0

Reinhard Zumkeller, Dec 08 2002

For n>0: 0A070939(n)+1, 0A070939(n). - Reinhard Zumkeller, Mar 07 2008

Row lengths in triangle A119709. - Reinhard Zumkeller, Aug 14 2013

			n=10 -> '1010' contains 5 different binary numbers: '0' (b0bb or bbb0), '1' (1bbb or bb1b), '10' (10bb or bb10), '101' (101b) and '1010' itself, therefore a(10)=5.

Alois P. Heinz, Table of n, a(n) for n = 0..16384 (first 1001 terms from Reinhard Zumkeller)

Cf. A078823, A078826, A078824, A007088, A141297, A144623, A144624.

a078822 = length . a119709_row
import Numeric (showIntAtBase)
-- Reinhard Zumkeller, Aug 13 2013, Sep 14 2011

a:= n-> (s-> nops({seq(seq(parse(s[i..j]), i=1..j),
        j=1..length(s))}))(""||(convert(n, binary))):
seq(a(n), n=0..85);  # Alois P. Heinz, Jan 20 2021

a[n_] := (id = IntegerDigits[n, 2]; nd = Length[id]; Length[ Union[ Flatten[ Table[ id[[j ;; k]], {j, 1, nd}, {k, j, nd}], 1] //. {0, b__} :> {b}]]); Table[ a[n], {n, 0, 85}] (* Jean-François Alcover, Dec 01 2011 *)

a(n) = {if (n==0, 1, vb = binary(n); vf = []; for (i=1, #vb, for (j=1, #vb - i + 1, pvb = vector(j, k, vb[i+k-1]); f = subst(Pol(pvb), x, 2); vf = Set(concat(vf, f)); ); ); #vf); } \\ Michel Marcus, May 08 2016; corrected Jun 13 2022

def a(n): return 1 if n == 0 else len(set(((((2<>i for i in range(n.bit_length()) for l in range(n.bit_length()-i)))
print([a(n) for n in range(64)]) # Michael S. Branicky, Jul 28 2022

For k>0: a(2^k-2) = 2*(k-1)+1, a(2^k-1) = k, a(2^k) = k+2;
for k>1: a(2^k+1) = k+2;
for k>0: a(2^k-1) = A078824(2^k-1), a(2^k) = A078824(2^k).

A225243 Irregular triangle read by rows, where row n contains the distinct primes that are contained in the binary representation of n as substrings; first row = [1] by convention.

Original entry on oeis.org

1, 2, 3, 2, 2, 5, 2, 3, 3, 7, 2, 2, 2, 5, 2, 3, 5, 11, 2, 3, 2, 3, 5, 13, 2, 3, 7, 3, 7, 2, 2, 17, 2, 2, 3, 19, 2, 5, 2, 5, 2, 3, 5, 11, 2, 3, 5, 7, 11, 23, 2, 3, 2, 3, 2, 3, 5, 13, 2, 3, 5, 11, 13, 2, 3, 7, 2, 3, 5, 7, 13, 29, 2, 3, 7, 3, 7, 31, 2, 2, 2, 17

Offset: 1

Reinhard Zumkeller, Aug 14 2013

Row n = primes in row n of tables A165416 or A119709.

			.   n   T(n,*)              |  in binary
.  ---  --------------------|-------------------------------------------
.   1:  1                   |  00001:  .
.   2:  2                   |  00100:  ___10
.   3:  3                   |  00011:  ___11
.   4:  2                   |  00100:  __10_
.   5:  2  5                |  00101:  ___10 _11__
.   6:  2  3                |  00110:  ___10 __11_
.   7:  3  7                |  00111:  __11_ __111
.   8:  2                   |  01000:  _10__
.   9:  2                   |  01001:  _10__
.  10:  2  5                |  01010:  _10__ _101_
.  11:  2  3  5 11          |  01011:  _10__ ___11 _101_ 01011
.  12:  2  3                |  01100:  ___10 _11__
.  13:  2  3  5 13          |  01101:  __10_ _11__ __101 01101
.  14:  2  3  7             |  01110:  ___10 _11__ _111_
.  15:  3  7                |  01111:  _11__ _111_
.  16:  2                   |  10000:  10___
.  17:  2 17                |  10001:  10___ 10001
.  18:  2                   |  10010:  10___
.  19:  2  3 19             |  10011:  10___ ___11 10011
.  20:  2  5                |  10100:  10___ 101__
.  21:  2  5                |  10101:  10___ 101__
.  22:  2  3  5 11          |  10110:  10___ __11_ 101__ 10110
.  23:  2  3  5  7 11 23    |  10111:  10___ __11_ 101__ __111 1011_ 10111
.  24:  2  3                |  11000:  _10__ 11___
.  25:  2  3                |  11001:  _10__ 11___ .

Reinhard Zumkeller, Rows n = 1..1024 of table, flattened
Michael De Vlieger, Plot of pi(p) such that T(n,k) = p for n = 1..4096.

Cf. A078826 (row lengths), A078832 (left edge), A078833 (right edge), A004676, A007088.

a225243 n k = a225243_tabf !! (n-1) !! (k-1)
a225243_row n = a225243_tabf !! (n-1)
a225243_tabf = [1] : map (filter ((== 1) . a010051')) (tail a165416_tabf)

Array[Union@ Select[FromDigits[#, 2] & /@ Rest@ Subsequences@ IntegerDigits[#, 2], PrimeQ] &, 34] /. {} -> {1} // Flatten (* Michael De Vlieger, Jan 26 2022 *)

from sympy import isprime
from itertools import count, islice
def primess(n):
    b = bin(n)[2:]
    ss = (int(b[i:j], 2) for i in range(len(b)) for j in range(i+2, len(b)+1))
    return sorted(set(k for k in ss if isprime(k)))
def agen():
    yield 1
    for n in count(2):
        yield from primess(n)
print(list(islice(agen(), 82))) # Michael S. Branicky, Jan 26 2022

A078833 Greatest prime contained as binary substring in binary representation of n>1, a(1)=1.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 7, 2, 2, 5, 11, 3, 13, 7, 7, 2, 17, 2, 19, 5, 5, 11, 23, 3, 3, 13, 13, 7, 29, 7, 31, 2, 2, 17, 17, 2, 37, 19, 19, 5, 41, 5, 43, 11, 13, 23, 47, 3, 17, 3, 19, 13, 53, 13, 23, 7, 7, 29, 59, 7, 61, 31, 31, 2, 2, 2, 67, 17, 17, 17, 71, 2, 73, 37, 37, 19, 19, 19, 79, 5, 17

Offset: 1

Reinhard Zumkeller, Dec 08 2002

a(n) = A039634(n) for n<=44, but a(45) = 13 <> 11 = A039634(45);
for n>1: a(n) = n iff n is prime.
a(n) = A225243(n, A078826(n)). - Reinhard Zumkeller, Aug 14 2013

			n=12 -> '1100' contains 2 binary substrings which are primes: '11' (11bb) and '10' (b11b); 3='11' is the greater one, therefore a(12)=3.

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

Cf. A078832, A078826, A078822, A007088, A006530.

a078833 = last . a225243_row  -- Reinhard Zumkeller, Aug 14 2013

A078827 Number of primes contained as binary substrings in binary representation of n, counted with repetitions.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 2, 3, 1, 1, 3, 4, 2, 4, 4, 5, 1, 2, 2, 3, 3, 4, 5, 7, 2, 2, 5, 6, 4, 7, 6, 8, 1, 1, 3, 3, 2, 4, 4, 5, 3, 4, 5, 7, 5, 7, 8, 10, 2, 3, 3, 4, 5, 7, 7, 9, 4, 4, 8, 10, 6, 10, 9, 11, 1, 1, 2, 3, 3, 4, 4, 6, 2, 3, 5, 6, 4, 6, 6, 8, 3, 4, 5, 7, 5, 6, 8, 10, 5, 6, 8, 9, 8, 11, 11, 13, 2, 3, 4, 4, 3

Offset: 0

Reinhard Zumkeller, Dec 08 2002

			n=7 -> '111' contains 3 binary substrings which are primes: '11' (11b), '11' (b11) and '111' itself, therefore a(7)=2.

Cf. A078826, A078822, A007088, A001222, A078828.

A078832 Smallest prime contained as binary substring in binary representation of n>1, a(1)=1.

Original entry on oeis.org

1, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 1

Reinhard Zumkeller, Dec 08 2002

a(n)<=3 and for n>1: a(n)>=2 and a(n)=3 iff n=2^k-1, k>1.

a(n) = A225243(n,1). - Reinhard Zumkeller, Aug 14 2013

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

Cf. A078833, A078826, A078822, A007088, A020639.

Cf. A030308, A010051, A000225.

a078832 = head . a225243_row  -- Reinhard Zumkeller, Aug 14 2013

For n > 1: a(n) = A036987(n) + 2. Reinhard Zumkeller, Aug 14 2013

A143792 a(n) = the number of distinct prime divisors, p, of n that, when p is represented in binary, each p occurs at least once in the binary representation of n.

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Sep 01 2008

a(2^k * p) = 2, where k = any positive integer and p = any odd prime.
a(p) = 1, where p = any prime.
a(2^k) = 1, where k = any positive integer.
a(n) <= A078826(n). - Reinhard Zumkeller, Sep 08 2008
Size of intersection of n-th rows of tables A225243 and A027748. - Reinhard Zumkeller, Aug 14 2013

			60 in binary is 111100. The distinct primes dividing 60 are 2 (which is 10 in binary), 3 (11 in binary) and 5 (101) in binary. The string 10 does occur within 111100 like so: 111(10)0. The string 11 also occurs (multiple times) within 111100, in one way like so: (11)1100. But the string 101 does not occur in 111100. Since 2 and 3 occur within 60 (when each of these numbers is written in binary), but 5 does not, then a(60) = 2.

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

Cf. A143791.

import Data.List (intersect)
a143792 n = length $ a225243_row n `intersect` a027748_row (fromIntegral n)
-- Reinhard Zumkeller, Aug 14 2013

f[n_] := Block[{nb = ToString@ FromDigits@ IntegerDigits[n, 2], psb = ToString@ FromDigits@ IntegerDigits[ #, 2] & /@ First@ Transpose@ FactorInteger@ n, c = 0, k = 1}, lmt = 1 + Length@ psb; While[k < lmt, If[ StringCount[nb, psb[[k]]] > 0, c++ ]; k++ ]; c]; f[1] = 0; Array[f, 105] (* Robert G. Wilson v, Sep 22 2008 *)

More terms from Robert G. Wilson v, Sep 22 2008

A078829 Numbers having exactly one prime contained as binary substring in binary representation of n.

Original entry on oeis.org

2, 3, 4, 8, 9, 16, 18, 32, 33, 36, 64, 65, 66, 72, 128, 129, 130, 132, 144, 256, 258, 260, 264, 265, 288, 289, 512, 513, 516, 520, 528, 530, 576, 578, 1024, 1025, 1026, 1032, 1040, 1056, 1057, 1060, 1152, 1156, 2048, 2049, 2050, 2052, 2064, 2080, 2112, 2114

Offset: 1

Reinhard Zumkeller, Dec 08 2002

A078826(a(n)) = 1; A078830 is a subsequence;

for k>2 also floor(a(k)/2) belongs to the sequence.

			n=18 -> '10010' contains only 1 distinct binary substring which is prime: '10' (10bbb or bbb10), therefore 18 is a term.

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

Cf. A078826, A078830, A007088.

Cf. A225243.

a078829 n = a078829_list !! (n-1)
a078829_list = filter ((== 1) . a078826) [1..]
-- Reinhard Zumkeller, Jul 17 2015

primeCount[n_] := (bits = IntegerDigits[n, 2]; lg = Length[bits]; Reap[Do[If[PrimeQ[p = FromDigits[bits[[i ;; j]], 2]], Sow[p]], {i, 1, lg-1}, {j, i+1, lg}]][[2, 1]] // Union // Length); primeCount[1] = 0; Select[Range[3000], primeCount[#] == 1 &] (* Jean-François Alcover, May 23 2013 *)

A078831 Numbers n with unique occurrence of all binary substrings representing primes in binary representation of n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13, 16, 17, 19, 24, 25, 32, 33, 35, 48, 49, 64, 65, 67, 96, 97, 128, 129, 131, 192, 193, 256, 257, 259, 384, 385, 512, 513, 515, 768, 769, 1024, 1025, 1027, 1536, 1537, 2048, 2049, 2051, 3072, 3073, 4096, 4097, 4099, 6144, 6145

Offset: 1

Reinhard Zumkeller, Dec 08 2002

A078826(a(n)) = A078827(a(n)); A078830 is a subsequence.

			n=12 -> '1100' contains two substrings representing distinct primes: '10'=2 and '11'=3, therefore 12 is a term.

Ray Chandler, Table of n, a(n) for n = 1..110

Cf. A078826, A078827, A078830, A007088.

Extended by Ray Chandler, Nov 03 2008

A329873 a(n) is the number of distinct prime numbers whose binary digits appear in order but not necessarily as consecutive digits in the binary representation of n.

Original entry on oeis.org

0, 0, 1, 1, 1, 3, 2, 2, 1, 3, 3, 5, 2, 5, 3, 2, 1, 4, 3, 6, 3, 6, 5, 6, 2, 5, 5, 6, 3, 6, 3, 3, 1, 4, 4, 7, 3, 9, 6, 7, 3, 8, 6, 9, 5, 8, 6, 8, 2, 6, 5, 7, 5, 8, 6, 8, 3, 6, 6, 9, 3, 8, 4, 3, 1, 4, 4, 8, 4, 9, 7, 9, 3, 11, 9, 11, 6, 11, 7, 10, 3, 8, 8, 12, 6

Offset: 0

Rémy Sigrist, Nov 23 2019

This sequence is unbounded.

			The first terms, alongside the binary representations of n and of the corresponding prime numbers, are:
  n   a(n)  bin(n)  {bin(p)}
  --  ----  ------  --------------------
   0     0       0  {}
   1     0       1  {}
   2     1      10  {10}
   3     1      11  {11}
   4     1     100  {10}
   5     3     101  {10, 11, 101}
   6     2     110  {10, 11}
   7     2     111  {11, 111}
   8     1    1000  {10}
   9     3    1001  {10, 11, 101}
  10     3    1010  {10, 11, 101}
  11     5    1011  {10, 11, 101, 111, 1011}
  12     2    1100  {10, 11}

Rémy Sigrist, Table of n, a(n) for n = 0..16384

Cf. A007306, A036987, A078826, A303077.

b:= proc(n) option remember; `if`(n=0, {0},
      map(x-> [x, 2*x+r][], b(iquo(n, 2, 'r'))))
    end:
a:= n-> nops(select(isprime, b(n))):
seq(a(n), n=0..84);  # Alois P. Heinz, Jan 26 2022

a(n,base=2) = { my (b=digits(n,base), s=[0]); for (k=1, #b, s = setunion(s, apply(o -> base*o+b[k], s))); #select(isprime, s) }

A078826(n) <= a(n) <= A007306(n+1).
a(2*n) = a(n) + A036987(n) for any n > 0.
a(2^n) = 1 for any n > 0.

cp's OEIS Frontend

A071338 Duplicate of A078826.

Views

Author

Keywords

A078822 Number of distinct binary numbers contained as substrings in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A225243 Irregular triangle read by rows, where row n contains the distinct primes that are contained in the binary representation of n as substrings; first row = [1] by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

A078833 Greatest prime contained as binary substring in binary representation of n>1, a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

A078827 Number of primes contained as binary substrings in binary representation of n, counted with repetitions.

Views

Author

Keywords

Examples

Crossrefs

A078832 Smallest prime contained as binary substring in binary representation of n>1, a(1)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Formula

A143792 a(n) = the number of distinct prime divisors, p, of n that, when p is represented in binary, each p occurs at least once in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A078829 Numbers having exactly one prime contained as binary substring in binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell